Submission #636418

#	Time	Username	Problem	Language	Result	Execution time	Memory
636418		tht2005	Copy and Paste 3 (JOI22_copypaste3)	C++17	5 / 100	566 ms	115108 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

#define N 2503

struct state {
    int i, j;
    long long d;
    bool operator< (const state& b) const {
        return d > b.d;
    }
};

char s[N];
long long f[N][N];

int main() {
    int n, A, B, C;
    scanf("%d %s %d %d %d", &n, s, &A, &B, &C);
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    priority_queue<state> q;
    q.push({0, 0, 0});
    while(!q.empty()) {
        state _ = q.top();
        q.pop();
        if(_.d != f[_.i][_.j]) {
            continue;
        }
        int i = _.i, j = _.j;
        if(i == n) {
            printf("%lld", _.d);
            return 0;
        }
        if(f[i + 1][j] > _.d + A) {
            q.push({i + 1, j, f[i + 1][j] = _.d + A});
        }
        if(f[0][i] > _.d + B) {
            q.push({0, i, f[0][i] = _.d + B});
        }
        if(i + j <= n && f[i + j][j] > _.d + C) {
            q.push({i + j, j, f[i + j][j] = _.d + C});
        }
    }
//    f[i][j] -> f[i + 1][j] + A
//            -> f[0][i] + B
//            -> f[i + j][j] + C
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d %s %d %d %d", &n, s, &A, &B, &C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 5 / 5
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38