#include<bits/stdc++.h> #define MAX 200000 #define FOR(i,a,b) for(int i=a;i<b;++i) #define REP(i,n) FOR(i,0,n) #define FORD(i,a, b) for(int i=a;i<=b;++i) #define ull unsigned long long using namespace std; ull max(long long a, long long b) { return a > b ? a : b; } ull furnaces[MAX+1]; ull moments[MAX+1]; ull outcomes[MAX+1]; ull momentsSum = 0; ull sum(int j, int i) { if(j == 0) { return max(0, moments[0] - furnaces[i]); } return max(outcomes[j-1] + furnaces[i], moments[j] - furnaces[i]); } int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; REP(i, n) { cin >> moments[i]; momentsSum += moments[i]; } REP(i, m) { cin >> furnaces[i]; } REP(i, m) { ull sumOfMoments = 0; outcomes[0] = sum(0, i); FORD(j, 1, n) { outcomes[j] = sum(j, i); } REP(j, n) sumOfMoments += outcomes[j]; cout << sumOfMoments + n*furnaces[i] - momentsSum << endl; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include<bits/stdc++.h> #define MAX 200000 #define FOR(i,a,b) for(int i=a;i<b;++i) #define REP(i,n) FOR(i,0,n) #define FORD(i,a, b) for(int i=a;i<=b;++i) #define ull unsigned long long using namespace std; ull max(long long a, long long b) { return a > b ? a : b; } ull furnaces[MAX+1]; ull moments[MAX+1]; ull outcomes[MAX+1]; ull momentsSum = 0; ull sum(int j, int i) { if(j == 0) { return max(0, moments[0] - furnaces[i]); } return max(outcomes[j-1] + furnaces[i], moments[j] - furnaces[i]); } int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; REP(i, n) { cin >> moments[i]; momentsSum += moments[i]; } REP(i, m) { cin >> furnaces[i]; } REP(i, m) { ull sumOfMoments = 0; outcomes[0] = sum(0, i); FORD(j, 1, n) { outcomes[j] = sum(j, i); } REP(j, n) sumOfMoments += outcomes[j]; cout << sumOfMoments + n*furnaces[i] - momentsSum << endl; } } |