답안 #242870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242870	2020-06-29T14:03:15 Z	AmineWeslati	Feast (NOI19_feast)	C++14	71 / 100	210 ms	145016 KB

feast

//Never stop trying
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//s.order_of_key(), *s.find_by_order()

using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;

typedef pair<int,int> pi;
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;

#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

const int MOD = 1e9+7; //998244353
const ll INF = 1e18;
const int nx[4]={0,0,1,-1}, ny[4]={1,-1,0,0}; //right left down up

int t[300001];
int memo[3000][3001][2];
int N,K;

int solve(int i, int r, int st){
   if(!r && i==N) return 0;
   if(i==N) return -INF;
   if(memo[i][r][st]!=-1) return memo[i][r][st];

   int ans=solve(i+1,r,0);
   if(st) ans=max(ans,solve(i+1,r,1)+t[i]);
   ans=max(ans,solve(i+1,r-1,1)+t[i]);

   return memo[i][r][st]=ans;
}

int32_t main(){
   boost;
   memset(memo,-1,sizeof(memo));
   cin>>N>>K;
   int cnt=0;
   for(int i=0; i<N; i++){
      cin>>t[i];
      if(t[i]<0) cnt++;
   }

   if(cnt==0 ||(cnt==1 && K>1)){
      int res=0;
      for(int i=0; i<N; i++) if(t[i]>0) res+=t[i];
      cout << res << endl;
   }
   else if(cnt==1){
      int s=0,ss=0,sss=0;
      int idx=0;
      while(t[idx]>=0){s+=t[idx]; idx++;}
      sss+=t[idx]; idx++;
      while(idx<N && t[idx]>=0){ss+=t[idx]; idx++;}
      cout << max(max(s,ss),s+ss+sss) << endl;
   }
   else if(K==1){
      int s=0;
      int res=0;
      for(int i=0; i<N; i++){
         s+=t[i];
         res=max(res,s);
         if(s<=0) s=0;
      }
      cout << res << endl;
   }
   else if(N<=3005){
      int res=0;
      for(int i=0; i<=K; i++) res=max(res,solve(0,i,0));
      cout << res << endl;
   }


   return 0;
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	144632 KB	Output is correct
2	Correct	120 ms	144808 KB	Output is correct
3	Correct	120 ms	144760 KB	Output is correct
4	Correct	122 ms	144776 KB	Output is correct
5	Correct	118 ms	144888 KB	Output is correct
6	Correct	115 ms	144700 KB	Output is correct
7	Correct	111 ms	144760 KB	Output is correct
8	Correct	117 ms	144712 KB	Output is correct
9	Correct	111 ms	144808 KB	Output is correct
10	Correct	112 ms	144764 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	144632 KB	Output is correct
2	Correct	95 ms	144760 KB	Output is correct
3	Correct	97 ms	144632 KB	Output is correct
4	Correct	98 ms	144760 KB	Output is correct
5	Correct	113 ms	144760 KB	Output is correct
6	Correct	97 ms	144632 KB	Output is correct
7	Correct	99 ms	144760 KB	Output is correct
8	Correct	120 ms	144888 KB	Output is correct
9	Correct	116 ms	144888 KB	Output is correct
10	Correct	106 ms	144760 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	116 ms	144632 KB	Output is correct
2	Correct	120 ms	144760 KB	Output is correct
3	Correct	119 ms	144808 KB	Output is correct
4	Correct	123 ms	144760 KB	Output is correct
5	Correct	120 ms	144760 KB	Output is correct
6	Correct	120 ms	144760 KB	Output is correct
7	Correct	121 ms	144888 KB	Output is correct
8	Correct	124 ms	144796 KB	Output is correct
9	Correct	132 ms	144760 KB	Output is correct
10	Correct	122 ms	144888 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	76 ms	141304 KB	Output is correct
2	Correct	74 ms	141304 KB	Output is correct
3	Correct	75 ms	141304 KB	Output is correct
4	Correct	82 ms	141304 KB	Output is correct
5	Correct	83 ms	141304 KB	Output is correct
6	Correct	79 ms	141280 KB	Output is correct
7	Correct	75 ms	141304 KB	Output is correct
8	Correct	75 ms	141304 KB	Output is correct
9	Correct	75 ms	141304 KB	Output is correct
10	Correct	76 ms	141304 KB	Output is correct

Subtask #5
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	76 ms	141304 KB	Output is correct
2	Correct	74 ms	141304 KB	Output is correct
3	Correct	75 ms	141304 KB	Output is correct
4	Correct	82 ms	141304 KB	Output is correct
5	Correct	83 ms	141304 KB	Output is correct
6	Correct	79 ms	141280 KB	Output is correct
7	Correct	75 ms	141304 KB	Output is correct
8	Correct	75 ms	141304 KB	Output is correct
9	Correct	75 ms	141304 KB	Output is correct
10	Correct	76 ms	141304 KB	Output is correct
11	Correct	76 ms	141304 KB	Output is correct
12	Correct	76 ms	141256 KB	Output is correct
13	Correct	88 ms	141352 KB	Output is correct
14	Correct	79 ms	141304 KB	Output is correct
15	Correct	75 ms	141304 KB	Output is correct
16	Correct	76 ms	141304 KB	Output is correct
17	Correct	78 ms	141304 KB	Output is correct
18	Correct	77 ms	141304 KB	Output is correct
19	Correct	76 ms	141304 KB	Output is correct
20	Correct	78 ms	141304 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	76 ms	141304 KB	Output is correct
2	Correct	74 ms	141304 KB	Output is correct
3	Correct	75 ms	141304 KB	Output is correct
4	Correct	82 ms	141304 KB	Output is correct
5	Correct	83 ms	141304 KB	Output is correct
6	Correct	79 ms	141280 KB	Output is correct
7	Correct	75 ms	141304 KB	Output is correct
8	Correct	75 ms	141304 KB	Output is correct
9	Correct	75 ms	141304 KB	Output is correct
10	Correct	76 ms	141304 KB	Output is correct
11	Correct	76 ms	141304 KB	Output is correct
12	Correct	76 ms	141256 KB	Output is correct
13	Correct	88 ms	141352 KB	Output is correct
14	Correct	79 ms	141304 KB	Output is correct
15	Correct	75 ms	141304 KB	Output is correct
16	Correct	76 ms	141304 KB	Output is correct
17	Correct	78 ms	141304 KB	Output is correct
18	Correct	77 ms	141304 KB	Output is correct
19	Correct	76 ms	141304 KB	Output is correct
20	Correct	78 ms	141304 KB	Output is correct
21	Correct	135 ms	141432 KB	Output is correct
22	Correct	210 ms	141432 KB	Output is correct
23	Correct	149 ms	141560 KB	Output is correct
24	Correct	133 ms	141432 KB	Output is correct
25	Correct	140 ms	141432 KB	Output is correct
26	Correct	147 ms	141548 KB	Output is correct
27	Correct	150 ms	141560 KB	Output is correct
28	Correct	131 ms	141432 KB	Output is correct
29	Correct	127 ms	141432 KB	Output is correct
30	Correct	123 ms	141432 KB	Output is correct

Subtask #7
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	144632 KB	Output is correct
2	Correct	120 ms	144808 KB	Output is correct
3	Correct	120 ms	144760 KB	Output is correct
4	Correct	122 ms	144776 KB	Output is correct
5	Correct	118 ms	144888 KB	Output is correct
6	Correct	115 ms	144700 KB	Output is correct
7	Correct	111 ms	144760 KB	Output is correct
8	Correct	117 ms	144712 KB	Output is correct
9	Correct	111 ms	144808 KB	Output is correct
10	Correct	112 ms	144764 KB	Output is correct
11	Correct	99 ms	144632 KB	Output is correct
12	Correct	95 ms	144760 KB	Output is correct
13	Correct	97 ms	144632 KB	Output is correct
14	Correct	98 ms	144760 KB	Output is correct
15	Correct	113 ms	144760 KB	Output is correct
16	Correct	97 ms	144632 KB	Output is correct
17	Correct	99 ms	144760 KB	Output is correct
18	Correct	120 ms	144888 KB	Output is correct
19	Correct	116 ms	144888 KB	Output is correct
20	Correct	106 ms	144760 KB	Output is correct
21	Correct	116 ms	144632 KB	Output is correct
22	Correct	120 ms	144760 KB	Output is correct
23	Correct	119 ms	144808 KB	Output is correct
24	Correct	123 ms	144760 KB	Output is correct
25	Correct	120 ms	144760 KB	Output is correct
26	Correct	120 ms	144760 KB	Output is correct
27	Correct	121 ms	144888 KB	Output is correct
28	Correct	124 ms	144796 KB	Output is correct
29	Correct	132 ms	144760 KB	Output is correct
30	Correct	122 ms	144888 KB	Output is correct
31	Correct	76 ms	141304 KB	Output is correct
32	Correct	74 ms	141304 KB	Output is correct
33	Correct	75 ms	141304 KB	Output is correct
34	Correct	82 ms	141304 KB	Output is correct
35	Correct	83 ms	141304 KB	Output is correct
36	Correct	79 ms	141280 KB	Output is correct
37	Correct	75 ms	141304 KB	Output is correct
38	Correct	75 ms	141304 KB	Output is correct
39	Correct	75 ms	141304 KB	Output is correct
40	Correct	76 ms	141304 KB	Output is correct
41	Correct	76 ms	141304 KB	Output is correct
42	Correct	76 ms	141256 KB	Output is correct
43	Correct	88 ms	141352 KB	Output is correct
44	Correct	79 ms	141304 KB	Output is correct
45	Correct	75 ms	141304 KB	Output is correct
46	Correct	76 ms	141304 KB	Output is correct
47	Correct	78 ms	141304 KB	Output is correct
48	Correct	77 ms	141304 KB	Output is correct
49	Correct	76 ms	141304 KB	Output is correct
50	Correct	78 ms	141304 KB	Output is correct
51	Correct	135 ms	141432 KB	Output is correct
52	Correct	210 ms	141432 KB	Output is correct
53	Correct	149 ms	141560 KB	Output is correct
54	Correct	133 ms	141432 KB	Output is correct
55	Correct	140 ms	141432 KB	Output is correct
56	Correct	147 ms	141548 KB	Output is correct
57	Correct	150 ms	141560 KB	Output is correct
58	Correct	131 ms	141432 KB	Output is correct
59	Correct	127 ms	141432 KB	Output is correct
60	Correct	123 ms	141432 KB	Output is correct
61	Incorrect	121 ms	145016 KB	Output isn't correct
62	Halted	0 ms	0 KB	-

답안 #242870

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 8.0 / 8.0

Subtask #3 18.0 / 18.0

Subtask #4 10.0 / 10.0

Subtask #5 11.0 / 11.0

Subtask #6 20.0 / 20.0

Subtask #7 0 / 29.0

Subtask #1
4.0 / 4.0

Subtask #2
8.0 / 8.0

Subtask #3
18.0 / 18.0

Subtask #4
10.0 / 10.0

Subtask #5
11.0 / 11.0

Subtask #6
20.0 / 20.0

Subtask #7
0 / 29.0