Submission #987747

#TimeUsernameProblemLanguageResultExecution timeMemory
987747activedeltorreShopping Plans (CCO20_day2problem3)C++14
15 / 25
163 ms33564 KiB
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; //ifstream cin("a.in"); //ofstream cout("a.out"); long long inf=1e9+10; struct node { long long layer,sum,lst,biti; }; struct cmp { bool operator()(node a,node b) { return a.sum>b.sum; } }; priority_queue<node,vector<node>,cmp>pq; vector<long long >arr; vector<long long >adj[200005]; long long cost[200005]; vector<long long>ord; bool cmp2(long long a,long long b) { return cost[a]<cost[b]; } int y[200005]; signed main() { long long n,m,k,i,a,b,x; 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=inf,poz=m; for(i=1; i<=m; i++) { cin>>x>>y[i]; if(x==0) { adj[i].push_back(0); } sort(adj[i].begin(),adj[i].end()); if(adj[i].size()<x) { for(long long j=1; j<=k; j++) { cout<<-1<<'\n'; } return 0; } 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) { cost[i]=adj[i][1]; } else { cost[i]=inf; } ord.push_back(i); } sort(ord.begin(),ord.end(),cmp2); m--; for(i=0; i<ord.size(); i++) { if(cost[ord[i]]==inf) { m=i-1; break; } } node curr,curr2; cout<<sum<<'\n'; k--; if(m>=0) { pq.push({0,adj[ord[0]][1],1,1}); while(pq.size() && k && imp==0) { curr=pq.top(); pq.pop(); k--; cout<<curr.sum+sum<<'\n'; if(curr.lst==1 && curr.layer+1<=m) { curr2=curr; curr2.layer++; curr2.biti=1; curr2.sum=curr2.sum-adj[ord[curr.layer]][1]+adj[ord[curr.layer+1]][1]; pq.push(curr2); } if(curr.layer+1<=m) { curr2=curr; curr2.layer++; curr2.lst=1; curr2.biti=1; curr2.sum=curr2.sum+adj[ord[curr.layer+1]][1]; pq.push(curr2); } if(adj[ord[curr.layer]].size()>curr.lst+1 && curr.biti<y[ord[curr.layer]]) { curr2=curr; curr2.lst++; curr2.biti++; curr2.sum+=adj[ord[curr.layer]][curr2.lst]; pq.push(curr2); } if(adj[ord[curr.layer]].size()>curr.lst+1) { curr.sum=curr.sum-adj[ord[curr.layer]][curr.lst]+adj[ord[curr.layer]][curr.lst+1]; curr.lst++; pq.push(curr); } } 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:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   52 |         if(adj[i].size()<x)
      |            ~~~~~~~~~~~~~^~
Main.cpp:62:30: 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]
   62 |         for(long long  j=0; j<adj[i].size(); j++)
      |                             ~^~~~~~~~~~~~~~
Main.cpp:78:15: 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]
   78 |     for(i=0; i<ord.size(); i++)
      |              ~^~~~~~~~~~~
Main.cpp:115:43: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  115 |             if(adj[ord[curr.layer]].size()>curr.lst+1 && curr.biti<y[ord[curr.layer]])
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
Main.cpp:123:43: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  123 |             if(adj[ord[curr.layer]].size()>curr.lst+1)
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
Main.cpp:43:21: warning: unused variable 'minim' [-Wunused-variable]
   43 |     long long imp=0,minim=inf,poz=m;
      |                     ^~~~~
Main.cpp:43:31: warning: unused variable 'poz' [-Wunused-variable]
   43 |     long long imp=0,minim=inf,poz=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...