oj.uz

Submission #168103

# Submission time Handle Problem Language Result Execution time Memory
168103 2019-12-11T11:43:15 Z Pancake Candies (JOI18_candies) C++14
8 / 100
 1531 ms 357116 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
   
#include <x86intrin.h>
#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>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair                                     
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-7;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n, a[N];
ll dp[3333][3333][2];

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> n;
   for (int i = 1; i <= n; i ++) cin >> a[i];
   for (int i = 0; i <= n; i ++)
      for (int j = 1; j <= n; j ++)
         dp[i][j][0] = dp[i][j][1] = -inf;
   dp[0][0][0] = dp[0][0][0] = 0;
   for (int i = 1; i <= n; i ++)
      for (int j = 1; j <= i; j ++) {
         dp[i][j][0] = max (dp[i - 1][j][0], dp[i - 1][j][1]); 
         dp[i][j][1] = dp[i - 1][j - 1][0] + a[i];
      }
   for (int i = 1; i <= (n + 1) / 2; i ++)
      cout << max (dp[n][i][1], dp[n][i][0]) << endl;
}

main () {                                       
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}

Compilation message

candies.cpp: In function 'void Solve()':
candies.cpp:60:16: warning: operation on 'dp[0][0][0]' may be undefined [-Wsequence-point]
    dp[0][0][0] = dp[0][0][0] = 0;
    ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
candies.cpp: At global scope:
candies.cpp:70:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {                                       
       ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 71160 KB Output is correct
2 Correct 61 ms 71160 KB Output is correct
3 Correct 62 ms 71160 KB Output is correct
4 Correct 61 ms 71288 KB Output is correct
5 Correct 61 ms 71160 KB Output is correct
6 Correct 61 ms 71160 KB Output is correct
7 Correct 62 ms 71164 KB Output is correct
8 Correct 62 ms 71072 KB Output is correct
9 Correct 62 ms 71160 KB Output is correct
10 Correct 62 ms 71160 KB Output is correct
11 Correct 62 ms 71084 KB Output is correct
12 Correct 61 ms 71032 KB Output is correct
13 Correct 61 ms 71048 KB Output is correct
14 Correct 61 ms 71004 KB Output is correct
15 Correct 61 ms 71032 KB Output is correct
16 Correct 61 ms 71032 KB Output is correct
17 Correct 62 ms 71032 KB Output is correct
18 Correct 62 ms 71032 KB Output is correct
19 Correct 62 ms 71108 KB Output is correct
20 Correct 61 ms 71032 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 71160 KB Output is correct
2 Correct 61 ms 71160 KB Output is correct
3 Correct 62 ms 71160 KB Output is correct
4 Correct 61 ms 71288 KB Output is correct
5 Correct 61 ms 71160 KB Output is correct
6 Correct 61 ms 71160 KB Output is correct
7 Correct 62 ms 71164 KB Output is correct
8 Correct 62 ms 71072 KB Output is correct
9 Correct 62 ms 71160 KB Output is correct
10 Correct 62 ms 71160 KB Output is correct
11 Correct 62 ms 71084 KB Output is correct
12 Correct 61 ms 71032 KB Output is correct
13 Correct 61 ms 71048 KB Output is correct
14 Correct 61 ms 71004 KB Output is correct
15 Correct 61 ms 71032 KB Output is correct
16 Correct 61 ms 71032 KB Output is correct
17 Correct 62 ms 71032 KB Output is correct
18 Correct 62 ms 71032 KB Output is correct
19 Correct 62 ms 71108 KB Output is correct
20 Correct 61 ms 71032 KB Output is correct
21 Runtime error 1531 ms 357116 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -