oj.uz

Submission #47837

# Submission time Handle Problem Language Result Execution time Memory
47837 2018-05-08T05:56:09 Z TheDarkning Candies (JOI18_candies) C++17
8 / 100
 956 ms 395448 KB 
/**
                  ▄█▀ ▀█▀ ▄▀▄ █▀ █▄█▄█ ▄▀▄ █▀ ▄█▀
                  <⇋⇋⇋⋛∰≓⊂(⌒,_ゝ⌒)⊃≓∰⋛⇋⇋⇋>

            ♔♕♖♗♘♙ ☜❷☞✪ ィℋ६ ≈ ᗫẵℜℵĬŊĞ ✪☜❷☞ ♚♛♜♝♞♟
            ♔♕♖♗♘♙                             ♚♛♜♝♞♟
                      ˙·٠•●♥ Ƹ̵̡Ӝ̵̨̄Ʒ ♥●•٠·˙
                      916 921 919 673
**/

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <map>
#include <deque>
#include <assert.h>
#include <queue>
#include <string>
#include <memory.h>
#include <set>
#include <math.h>

#define sz(s) s.size()
#define pb emplace_back
#define fr first
#define sc second
#define mk make_pair
#define int long long
#define all(s) s.begin(), s.end()
#define ok puts("ok");

using namespace std;

const int N = 2e5 + 5;
const int inf = 1e18 + 7;

int n, ar[N], dp[5000][5000];

main(){
    cin >> n;
    for( int i = 1; i <= n; i++ ){
        scanf("%d", &ar[i]);
    }
    for( int i = 0; i <= n; i++ ){
        for( int j = 0; j <= n; j++ ){
            dp[ i ][ j ] = -inf;
        }
    }

    dp[ 0 ][ 0 ] = 0;

    dp[ 0 ][ 1 ] = 0;
    dp[ 1 ][ 1 ] = ar[ 1 ];

    for( int i = 2; i <= n; i++ ){
        int cur = 0;
        for( int j = 0; j <= i; j++ ){
            cur = dp[j][ i - 1 ];
            if( j )
                cur = max( cur, dp[ j - 1 ][ i - 2 ] + ar[ i ] );
            dp[ j ][ i ] = cur;
        }
    }
    for( int i = 1; i <= ( n + 1 ) / 2; i++ ){
        cout << dp[ i ][ n ] << endl;
    }
}

Compilation message

candies.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
candies.cpp: In function 'int main()':
candies.cpp:45:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d", &ar[i]);
                     ~~~~~~^
candies.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 39672 KB Output is correct
2 Correct 42 ms 39780 KB Output is correct
3 Correct 43 ms 40000 KB Output is correct
4 Correct 43 ms 40000 KB Output is correct
5 Correct 43 ms 40000 KB Output is correct
6 Correct 42 ms 40000 KB Output is correct
7 Correct 44 ms 40036 KB Output is correct
8 Correct 41 ms 40060 KB Output is correct
9 Correct 42 ms 40060 KB Output is correct
10 Correct 43 ms 40200 KB Output is correct
11 Correct 42 ms 40200 KB Output is correct
12 Correct 43 ms 40200 KB Output is correct
13 Correct 45 ms 40200 KB Output is correct
14 Correct 42 ms 40200 KB Output is correct
15 Correct 44 ms 40220 KB Output is correct
16 Correct 43 ms 40220 KB Output is correct
17 Correct 43 ms 40220 KB Output is correct
18 Correct 42 ms 40220 KB Output is correct
19 Correct 42 ms 40220 KB Output is correct
20 Correct 43 ms 40220 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 39672 KB Output is correct
2 Correct 42 ms 39780 KB Output is correct
3 Correct 43 ms 40000 KB Output is correct
4 Correct 43 ms 40000 KB Output is correct
5 Correct 43 ms 40000 KB Output is correct
6 Correct 42 ms 40000 KB Output is correct
7 Correct 44 ms 40036 KB Output is correct
8 Correct 41 ms 40060 KB Output is correct
9 Correct 42 ms 40060 KB Output is correct
10 Correct 43 ms 40200 KB Output is correct
11 Correct 42 ms 40200 KB Output is correct
12 Correct 43 ms 40200 KB Output is correct
13 Correct 45 ms 40200 KB Output is correct
14 Correct 42 ms 40200 KB Output is correct
15 Correct 44 ms 40220 KB Output is correct
16 Correct 43 ms 40220 KB Output is correct
17 Correct 43 ms 40220 KB Output is correct
18 Correct 42 ms 40220 KB Output is correct
19 Correct 42 ms 40220 KB Output is correct
20 Correct 43 ms 40220 KB Output is correct
21 Runtime error 956 ms 395448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -