Submission #1102323

#TimeUsernameProblemLanguageResultExecution timeMemory
1102323ioaneNile (IOI24_nile)C++17
17 / 100
2070 ms4292 KiB
#include <bits/stdc++.h> #define LL long long #define PB push_back #define MP make_pair #define F first #define S second #define FF fflush(stdout) #define d(C) C-'a' const LL N = 250005; const LL mod = 1000000007; using namespace std; std::vector<long long> calculate_costs( std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) { int n = W.size(); int q = E.size(); long long total_a = 0; // vector<pair<int, pair<int, int> > > v; vector<pair<int, int> > v; for (int i = 0; i < n; ++i){ // v.PB(MP(W[i], MP(A[i], B[i]))); v.PB(MP(W[i], A[i] - B[i])); total_a += A[i]; } sort(v.begin(), v.end()); std::vector<long long> result; for (int i_E = 0; i_E < q; ++i_E){ int d = E[i_E]; LL dp[n+1]; memset(dp, 0, (n+1) * sizeof(LL)); for (int i = 1; i < n; ++i){ LL ndp = dp[i-1]; int j = i - 1; while (j >= 0 && v[j].F + d >= v[i].F){ int profit = v[i].S + v[j].S; ndp = max(ndp, (j > 0 ? dp[j-1] : 0) + (LL)profit); --j; } dp[i] = ndp; } result.PB(total_a - dp[n-1]); } return result; } // IIIIIIIII OOOOO A NN N EEEEEEEEEE // I O O A A N N N E // I O O A A N N N E // I O O A A N N N E // I O O AAAAAAAAA N N N EEEEEEEE // I O O A A N N N E // I O O A A N N N E // I O O A A N N N E // IIIIIIIII OOOOO A A N NN EEEEEEEEEE ___ KAPANADZE
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...