제출 #569560

#제출 시각아이디문제언어결과실행 시간메모리
569560tarunares7250Cloud Computing (CEOI18_clo)C++17
100 / 100
576 ms1612 KiB
//ulimit -s unlimited #include <bits/stdc++.h> using namespace std; #define ll long long #define vl vector<ll> #define vi vector<int> #define vb vector<bool> #define pql priority_queue<long long> #define pqp priority_queue<pair<ll,ll> > #define pqs priority_queue<ll,vl,greater<ll> > #define md ((ll) 1e9+7) typedef struct node{ ll c,f,v; bool operator<(node &b) const{ if(f == b.f){ return (c>b.c); } else{ return (f>b.f); } } }node; void solve(){ ll i,j,k,n,m; cin>>n; vector<node> sc(n); vector<node> a; ll tc = 0; for(i=0;i<n;i++){ cin>>sc[i].c>>sc[i].f>>sc[i].v; sc[i].v *= -1; a.push_back(sc[i]); tc += sc[i].c; } cin>>m; vector<node> oc(m); for(i=0;i<m;i++){ cin>>oc[i].c>>oc[i].f>>oc[i].v; oc[i].c *= -1; a.push_back(oc[i]); } sort(a.begin(),a.end()); ll dp[tc+1]; bool isp[tc+1]; memset(isp,false,sizeof(isp)); for(i=0;i<=tc;i++){ dp[i] = -1e15; } dp[0] = 0; isp[0] = true; for(i=0;i<n+m;i++){ if(a[i].c>0){ for(j=tc;j>=a[i].c;j--){ if(isp[j-a[i].c]){ dp[j] = max(dp[j],dp[j-a[i].c]+a[i].v); isp[j] = true; } } } else{ for(j = 0;j<=tc+a[i].c;j++){ if(isp[j-a[i].c]){ dp[j] = max(dp[j],dp[j-a[i].c]+a[i].v); isp[j] = true; } } } } ll ans = 0; for(i=0;i<=tc;i++){ ans = max(ans,dp[i]); } cout<<ans<<"\n"; // for(auto c:a){ // cout<<c.c<<","<<c.f<<","<<c.v<<"\n"; // } } /* dp[i][j][k] = max profit till ith computer and jth order,k cores are remaining dp[i-1][j] , dp[j][i-1] , dp[i-1][j-1] */ int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int t; //cin >> t; t = 1; while(t--) solve(); return 0; } /* ll i,j,k,n,m; cin>>n; vector<node> sp(n); for(i=0;i<n;i++){ cin>>sp[i].c>>sp[i].f>>sp[i].v; } sort(sp.begin(),sp.end()); cin>>m; vector<node> od(m); for(i=0;i<m;i++){ cin>>od[i].c>>od[i].f>>od[i].v; } sort(od.begin(),od.end()); vector<vector<vl> > dp(n,vector<vl> (m,vl(51,0))); //dp[0][0][0] = 0; for(i=0;i<n;i++){ for(j=0;j<m;j++){ for(k=0;k<51;k++){ dp[i][j][k] = max({(j-1>=0?dp[i][j-1][k]:0),(i-1>=0?dp[i-1][j][k]:0), ((i-1>=0 && j-1>=0 && k-(sp[i].c - od[j].c)>=0 && sp[i].f>=od[j].f)?dp[i-1][j-1][k-(sp[i].c - od[j].c)] + od[j].v-sp[i].v:0), }); } } } ll ans = 0; for(k=0;k<=50;k++){ ans = max(ans,dp[n-1][m-1][k]); } cout<<ans<<"\n"; cout<<"sp"<<"\n"; for(i=0;i<n;i++){ cout<<sp[i].c<<","<<sp[i].f<<","<<sp[i].v<<"\n"; } cout<<"od\n"; for(i=0;i<m;i++){ cout<<od[i].c<<","<<od[i].f<<","<<od[i].v<<"\n"; } cout<<dp.size()<<"\n"; cout<<dp[0].size()<<"\n"; cout<<dp[0][0].size()<<"\n"; */

컴파일 시 표준 에러 (stderr) 메시지

clo.cpp: In function 'void solve()':
clo.cpp:28:12: warning: unused variable 'k' [-Wunused-variable]
   28 |     ll i,j,k,n,m;
      |            ^
#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...