Submission #565615

#	Time	Username	Problem	Language	Result	Execution time	Memory
565615		shrimb	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	464 KiB

xylophone

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include "xylophone.h"
#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

// #define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 5001;
int n;
int d[maxn];

int dp[maxn][maxn];
bool best[maxn][maxn];

bool rec (int i, int sm) {
    if (sm > n || sm < 1) return 0;
    if (i == n - 1) return 1;
    auto A = rec(i + 1, sm + d[i]);
    auto B = rec(i + 1, sm - d[i]);
    if (A) best[i][sm] = 1;
    else best[i][sm] = 0;
    return A || B;
}

void follow (int i, int sm) {
    answer(i + 1, sm);
    if (i >= n - 1) return;
    if (best[i][sm]) follow(i + 1, sm + d[i]);
    else follow(i + 1, sm - d[i]);
}

void solve(int N) {
    n = N;
    for (int i = 2 ; i <= n ; i++) d[i-2] = query(i-1,i);
    for (int i = 1 ; i <= n ; i++) {
        if (rec(0, i)) {
            follow(0, i);
            return;
        }
    }
}

Compilation message (stderr)

xylophone.cpp:18:1: warning: multi-line comment [-Wcomment]
   18 | //\
      | ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53