WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM576 Div2 Easy "TheExperimentDiv2"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12508

スポンジがどれほど水分を含んでいるのか計測を行った。
この実験が行われた部屋は側面が密閉されているため、2次元として考える事が出来る。

この部屋は幅がNセンチメートルあり、
天井にN個のドロップカウンター(雫を垂らす機械)が設置されている。
ドロップカウンター No.0 は部屋の左端から0.5センチの所に設置されており、
それから右側に1センチ間隔で No.N-1までのドロップカウンターが設置されている。
i番目のドロップカウンターは1分間にintensity[i] 回、雫を垂らす。

この部屋にはM個のスポンジも設置されている。
i番目(最初は0)のスポンジは天井からi+1センチ下に水平に設置されており、
その左端は部屋の左の壁からleftEnd[i]センチ離れた位置にある。
全てのスポンジは長さがちょうどLセンチであり、厚さは無視できる程薄くなっている。
それぞれのスポンジはその場所に落ちてきた雫を完全に吸収する。

それぞれのスポンジが、1分間あたりどれほどの雫を吸収するのかを返せ。

制約

1 <= N <= 50
1 <= intensity[i] <= 1000
1 <= M <= 50



考えた事

上にあるスポンジを優先的に計算し、
既にスポンジに吸収されたドロップカウンターを
重複して計算しないようにする。



ソースコード

class TheExperimentDiv2 {
public:
    vector <int> determineHumidity(vector <int> intensity, int L, vector <int> leftEnd){
        bool use[55];
        memset( use, false, sizeof(use) );
        
        int n = leftEnd.size();
        int m = intensity.size();
        vector<int> res;
        for( int i = 0; i < n; i++ ){
            res.push_back(0);
            for( int j = leftEnd[i]; j < m && j < leftEnd[i] + L; j++ ){
                if( use[j] ) continue;
                res[i] += intensity[j];
                use[j] = true;
            }
        }

        return res;
    }
};