Submission #895556

#TimeUsernameProblemLanguageResultExecution timeMemory
895556preskoSchools (IZhO13_school)C++14
10 / 100
45 ms20304 KiB
#include<iostream> #include<bits/stdc++.h> #define MAXN 300010 using namespace std; long long dp[MAXN][3];//long long pair<int,int> state[MAXN][3]; pair<int,int> city[MAXN]; //vector<pair<pair<int,int>,int>> order; int main() { int n,m,s; ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>s; state[0][0]={m,s}; state[0][1]={m,s}; state[0][2]={m,s}; for(int i=1;i<=n;i++) { cin>>city[i].first>>city[i].second; state[i][0]={m,s}; state[i][1]={m,s}; state[i][2]={m,s}; //order.push_back({city[i],i}); } //sort(order.begin(),order.end(),greater<pair<pair<int,int>,int>>()); for(int i=1;i<=n;i++) { int mus=city[i].first; int sp=city[i].second; for(int j=0;j<3;j++) { if(dp[i-1][j]>dp[i][0]) { dp[i][0]=dp[i-1][j]; state[i][0]=state[i-1][j]; } if(dp[i-1][j]+mus>dp[i][1] && state[i-1][j].first>0) { dp[i][1]=dp[i-1][j]+mus; state[i][1]=state[i-1][j]; state[i][1].first--; } if(dp[i-1][j]+sp>dp[i][2] && state[i-1][j].second>0) { dp[i][2]=dp[i-1][j]+sp; state[i][2]=state[i-1][j]; state[i][2].second--; } } } long long ans=0; for(int i=0;i<3;i++) { if(dp[n][i]>ans)ans=dp[n][i]; } cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...