Submission #1102331

#TimeUsernameProblemLanguageResultExecution timeMemory
1102331ioaneNile (IOI24_nile)C++17
67 / 100
2062 ms9044 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)); priority_queue<pair<LL, int> > pq; pq.push(MP((LL)v[0].S, v[0].F)); for (int i = 1; i < n; ++i){ LL ndp = dp[i-1]; int j = i - 1; while (pq.size() > 0){ pair<LL, int> sm = pq.top(); if (sm.S + d >= v[i].F){ ndp = max(ndp, sm.F + v[i].S); break; } pq.pop(); } dp[i] = ndp; pq.push(MP(dp[i-1] + v[i].S, v[i].F)); } LL ans = total_a - dp[n-1]; result.PB(ans); } 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

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:45:17: warning: unused variable 'j' [-Wunused-variable]
   45 |             int j = i - 1;
      |                 ^
#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...