Submission #590812

#	Time	Username	Problem	Language	Result	Execution time	Memory
590812		keta_tsimakuridze	Friend (IOI14_friend)	C++14	100 / 100	77 ms	16272 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;

// Find out best sample
/*
6
13 3 6 20 10 15
0 0 0 1 1 2 2 1 0 0


*/
void maxi(int &a, int b) {
    a = max(a, b);
}
int findSample(int n,int a[],int p[],int t[]){
    vector<vector< vector<int> > > dp(n);
    for(int i = 0; i < n; i++) dp[i].resize(2, vector<int> (2));
    for(int i = n - 1; i >= 0; i--) {
        if(i == 0) {
            for(int t = 0; t < 2; t++) {
                dp[i][1][t] += a[i];
            }
            return max(dp[i][0][0], max(dp[i][1][0], max(dp[i][0][1], dp[i][1][1])));
        }
        vector<vector<int> > dpn;
        dpn = dp[p[i]];
        for(int t2 = 0; t2 < 2; t2++) {

            if(t[i] == 0) {
                maxi(dpn[0][1], dp[i][1][t2] + a[i] + max(dp[p[i]][1][1], dp[p[i]][0][1]));
            }
            if(t[i] == 1) {
                for(int tt = 0; tt < 2; tt++)
                maxi(dpn[tt][0], dp[i][1][t2] + a[i] + max(dp[p[i]][tt][0], dp[p[i]][tt][1]));
            }
            if(t[i] == 2) {
                maxi(dpn[0][0], dp[i][1][t2] + a[i] + max(dp[p[i]][1][1], dp[p[i]][0][1]));
            }
        }

        t[i] = (t[i] < 2 ? 1 << t[i] : 3);
        for(int t2 = 0; t2 < 2; t2++) {
            maxi(dp[i][0][t2], dp[i][1][t2]);

            for(int tt1 = 0; tt1 < 2; tt1++) {
                for(int tt2 = 0; tt2 < 2; tt2++) {
                    if(!t2 && !tt2 && (t[i] & 1)) continue;
                    maxi(dpn[tt1 & (t[i] & 1 ? t2 : 1)][tt2 & (t[i] & 2 ? t2 : 1)], dp[p[i]][tt1][tt2] + dp[i][0][t2]);
                }
            }

        }
        dp[p[i]] = dpn;
    }
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:17:40: warning: control reaches end of non-void function [-Wreturn-type]
   17 |     vector<vector< vector<int> > > dp(n);
      |                                        ^

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31