Submission #987537

#TimeUsernameProblemLanguageResultExecution timeMemory
987537activedeltorreShopping Plans (CCO20_day2problem3)C++14
0 / 25
4059 ms531948 KiB
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; //ifstream cin("a.in"); //ofstream cout("a.out"); struct node { long long layer,sum,lst,tip; }; struct cmp { bool operator()(node a,node b) { if(a.sum==b.sum) { return a.layer<b.layer; } return a.sum>b.sum; } }; priority_queue<node,vector<node>,cmp>pq; vector<long long >arr; vector<long long >adj[200005]; int main() { long long n,m,k,i,a,b,x,y; long long sum=0; ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m>>k; for(i=1; i<=n; i++) { cin>>a>>b; adj[a].push_back(b); } long long imp=0,minim=1e9,poz=m; for(i=1; i<=m; i++) { cin>>x>>y; sort(adj[i].begin(),adj[i].end()); if(adj[i].size()==0) { imp=1; } else { long long vkuk=adj[i][0]; sum+=adj[i][0]; for(long long j=0; j<adj[i].size(); j++) { adj[i][j]-=vkuk; } if(adj[i].size()>=2) { if(adj[i][1]<=minim) { poz=i; } minim=min(minim,adj[i][1]); } } } swap(adj[m],adj[poz]); if(imp==1) { cout<<-1<<'\n'; } else { cout<<sum<<'\n'; } k--; node curr,curr2; pq.push({1,minim,0,0}); while(pq.size() && k && imp==0) { curr=pq.top(); pq.pop(); if(curr.lst!=0) { k--; cout<<curr.sum+sum<<'\n'; } else if(curr.lst==0 && curr.tip==1 && curr.layer!=m) { k--; cout<<curr.sum+sum<<'\n'; } if(curr.layer!=m+1) { if(curr.lst==0) { curr.sum-=minim; curr.tip=0; } else { curr.tip=1; } if(curr.lst+1<adj[curr.layer].size()) { curr2=curr; curr2.lst++; curr2.sum=curr2.sum-adj[curr.layer][curr.lst]+adj[curr.layer][curr.lst+1]; pq.push(curr2); } if(curr.layer+1<=m) { curr2=curr; curr2.sum+=minim; curr2.lst=0; curr2.layer++; pq.push(curr2); } } } while(k) { k--; cout<<-1<<'\n'; } return 0; } /* 5 2 7 1 5 1 3 2 3 1 6 2 1 1 1 1 1*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:52:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for(long long  j=0; j<adj[i].size(); j++)
      |                                 ~^~~~~~~~~~~~~~
Main.cpp:103:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             if(curr.lst+1<adj[curr.layer].size())
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...