Submission #1148895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148895		weakweakweak	Naan (JOI19_naan)	C++20	0 / 100	1 ms	1096 KiB

naan

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define fs first 
#define sc second

int n, l, target[6] = {0}, a[6][12010], st[6][12010];
ll sum[6][12010];
bool dp[12010][1<<6] = {0};
pii lst[12010][1<<6];

void outputans (int now) {
    int mask = (1<<n)-1;
    vector<int> v;
    vector<int> pos;
    while (mask > 0) {
        pii p = lst[now][mask];
        v.push_back(__lg(mask-p.sc)+1);
        now = p.fs, mask = p.sc;
        if (mask > 0) pos.push_back(now);
    }
    reverse(v.begin(), v.end());
    reverse(pos.begin(), pos.end());
    for (int x : pos) cout << x << ' ' << n*l << '\n';
    for (int x : v) cout << x << ' '; cout<< '\n';
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> l;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < l; j++) {
            int x;
            cin >> x;
            for (int k = 0; k < n; k++) a[i][j*n+k+1] = x;
            target[i] += x;
        }
        sum[i][0] = 0;
        for (int j = 1; j <= n*l; j++) sum[i][j] += sum[i][j-1] + a[i][j];
        for (int j = 1, k = 0; j <= n*l; j++) {
            if (sum[i][j]-sum[i][k] < target[i]) st[i][j] = -1;
            else {
                while (k+1<j and sum[i][j]-sum[i][k+1] >= target[i]) k++;
                // cout << i << ' ' << j << ' ' << k << '\n';
                st[i][j] = k;
            }
        }
    }

    for (int pos = 0; pos < n*l; pos++) dp[pos][0] = 1;
    for (int pos = 1; pos <= n*l; pos++) {
        for (int mask = 0; mask < (1<<n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask&(1<<i)) == 0) continue;
                if (st[i][pos] == -1) continue;
                if (dp[st[i][pos]][mask-(1<<i)]) dp[pos][mask] = 1, lst[pos][mask] = make_pair(st[i][pos], mask-(1<<i));

            }
            // cout << pos << ' ' << mask << ' ' << dp[pos][mask] << ' ' << mask << '\n';
        }
    }

    for (int pos = 1; pos <= n*l; pos++) if (dp[pos][(1<<n)-1]) outputans(pos);
    cout << "-1\n";
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 24
• Subtask 3: 0 / 71