fork(1) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <iomanip>
  13. #define dibs reserve
  14. #define OVER9000 1234567890
  15. #define patkan 9
  16. #define tisic 47
  17. #define soclose 1e-7
  18. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  19. #define chocolate win
  20. #define ff first
  21. #define ss second
  22. #define abs(x) ((x < 0)?-(x):(x))
  23. // mylittlepony
  24. using namespace std;
  25.  
  26. int main() {
  27. 	// freopen("nochange.in","r",stdin);
  28. 	// freopen("nochange.out","w",stdout);
  29.     cin.sync_with_stdio(0);
  30.  
  31.     int K,N;
  32.     cin >> K >> N;
  33.     vector<int> C(K), P(N);
  34.     for(int i =0; i < K; i++) cin >> C[i];
  35.     vector<int> Sc((1<<K),0);
  36.     for(int i =0; i < (1<<K); i++) for(int j =K-1; j >= 0; j--) {
  37.     	if((1<<j) <= i) break;
  38.     	Sc[i+(1<<j)] =Sc[i]+C[j];}
  39.     for(int i =0; i < N; i++) cin >> P[i];
  40.     vector<int> Sp(N+1,0);
  41.     for(int i =0; i < N; i++) Sp[i+1] =Sp[i]+P[i];
  42.  
  43.     // ak som prvych i zaplatil, co prve nezaplatim na mincu j?
  44.     vector< vector<int> > D(N+1, vector<int>(K,-1));
  45.     for(int i =0; i < K; i++) {
  46.     	int a =0; // prve co nezaplatim
  47.     	for(int j =0; j < N; j++) {
  48.     		while(a < N) {
  49.     			if(Sp[a+1]-Sp[j] <= C[i]) a++;
  50.     			else break;}
  51.     		D[j][i] =a;}
  52.     	D[N][i] =N;}
  53.  
  54.     // dynamika: kolko najviac zaplatim na mnozinu minci M?
  55.     vector<int> res((1<<K),0);
  56.     for(int i =1; i < (1<<K); i++) 
  57.     	for(int j =0; j < K; j++) if((i&(1<<j)) != 0)
  58.     		res[i] =max(res[i],D[res[i^(1<<j)]][j]);
  59.  
  60.     int ans =-1;
  61.     for(int i =0; i < (1<<K); i++)
  62.     	if(res[i] == N) ans =max(ans,Sc[(1<<K)-1]-Sc[i]);
  63.     cout << ans << "\n";
  64.     return 0;}
  65.  
  66. // look at my code
  67. // my code is amazing
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
5 5
1 2 3 4 7
1 5 3 4 3
stdout
copy 
-1
https://ideone.com/9YWtkL
usaco nov-13
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!