oj.uz

Submission #209679

# Submission time Handle Problem Language Result Execution time Memory
209679 2020-03-15T06:08:10 Z maomao90 Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 334 ms 262148 KB 
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1000000000

//#define TC

int K, n, m, A, B;
int V[1005], S[5005], T[5005];
int ans = -INF;

//dp(s, t, state) returns the maximum happiness from S[s to n-1] and T[t to n-1];
//state = 0 means that S[s-1] and T[t-1] were both not attended;
//state = 1 means that S[s-1] was attended but T[t-1] was not attended;
//state = 2 means that S[s-1] was not attended but T[t-1] was attended;
//state = 3 means that S[s-1] and T[t-1] were both attended;
//start = 0 means that he still have not started his trip;
//start = 1 means that his trip already started;
int memo[5005][5005][5][2];
int dp(int s, int t, int state, int start)
{
    if (t >= m) return 0;
    if (s >= n)
    {
        if (state == 1 || state == 3 || start == 0) return A + B * (m - t);
        else return B * (m - t);
    }
    if (memo[s][t][state][start] != INF) return memo[s][t][state][start];
    if (start == 0)
    {
        if (state == 0)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 0, 0), dp(s, t + 1, 0, 0) + B);
        }
        else if (state == 1)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 0, 0), dp(s, t + 1, 1, 0) + B);
        }
        else if (state == 2)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 2, 0), dp(s, t + 1, 0, 0) + A + B);
        }
        else if (state == 3)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 2, 0), dp(s, t + 1, 1, 0) + A + B);
        }
    }
    else
    {
        if (state == 0)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 0, 1) + B, dp(s, t + 1, 0, 1) + B);
        }
        else if (state == 1)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 0, 1) + A + B, dp(s, t + 1, 1, 1) + B);
        }
        else if (state == 2)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 2, 1) + B, dp(s, t + 1, 0, 1) + A + B);
        }
        else if (state == 3)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 2, 1) + A + B, dp(s, t + 1, 1, 1) + A + B);
        }
    }
    if (S[s] == T[t]) memo[s][t][state][start] = max(memo[s][t][state][start], dp(s + 1, t + 1, 3, 1) + V[S[s]]);
    return memo[s][t][state][start];
}

int main()
{
    #ifdef TC
    for (int i = 1; i <= 100; i++)
    {
        char temp[5];
        sprintf(temp, "%03d", i);
        string filein, fileout;
        filein = string(temp), fileout = string(temp);
        filein = "tests/" + filein + ".in";
        fileout = "out/" + fileout + ".out";
        freopen(filein.c_str(), "r", stdin);
        freopen(fileout.c_str(), "w", stdout);
        scanf("%d%d%d%d%d", &K, &n, &m, &A, &B);
        for (int i = 1; i <= K; i++) scanf("%d", &V[i]);
        for (int i = 0; i < n; i++) scanf("%d", &S[i]);
        for (int i = 0; i < m; i++) scanf("%d", &T[i]);
        for (int i = 0; i < n + 5; i++) for (int j = 0; j < m + 5; j++) for (int k = 0; k < 5; k++) for (int l = 0; l < 2; l++) memo[i][j][k][l] = INF;
        printf("%d\n", dp(0, 0, 3, 0));
        fclose(stdin);
        fclose(stdout);
    }
    #else
    scanf("%d%d%d%d%d", &K, &n, &m, &A, &B);
    for (int i = 1; i <= K; i++) scanf("%d", &V[i]);
    for (int i = 0; i < n; i++) scanf("%d", &S[i]);
    for (int i = 0; i < m; i++) scanf("%d", &T[i]);
    for (int i = 0; i < n + 5; i++) for (int j = 0; j < m + 5; j++) for (int k = 0; k < 5; k++) for (int l = 0; l < 2; l++) memo[i][j][k][l] = INF;
    printf("%d\n", dp(0, 0, 3, 0));
    return 0;
    #endif // TC
}

/*
Sample 4:
4 8 4 0 -3
1 2 3 4
3 1 2 1 1 4 1 1
1 2 3 4

Sample 5:
4 8 4 -3 0
1 2 3 4
3 1 2 1 1 4 1 1
1 2 3 4

Sample 6:
6 10 6 -2 -1
1 2 3 4 5 6
3 1 5 2 6 1 5 1 1 4
1 2 3 4 5 6
*/

Compilation message

VisitingSingapore.cpp: In function 'int main()':
VisitingSingapore.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d", &K, &n, &m, &A, &B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:98:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= K; i++) scanf("%d", &V[i]);
                                  ~~~~~^~~~~~~~~~~~~
VisitingSingapore.cpp:99:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < n; i++) scanf("%d", &S[i]);
                                 ~~~~~^~~~~~~~~~~~~
VisitingSingapore.cpp:100:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < m; i++) scanf("%d", &T[i]);
                                 ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1784 KB Output is correct
2 Correct 128 ms 38108 KB Output is correct
3 Correct 7 ms 2040 KB Output is correct
4 Correct 8 ms 4856 KB Output is correct
5 Correct 6 ms 2168 KB Output is correct
6 Correct 37 ms 13048 KB Output is correct
7 Correct 7 ms 1656 KB Output is correct
8 Correct 15 ms 5112 KB Output is correct
9 Correct 70 ms 22648 KB Output is correct
10 Correct 161 ms 44280 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1016 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 37 ms 11000 KB Output is correct
4 Correct 7 ms 1144 KB Output is correct
5 Correct 15 ms 3832 KB Output is correct
6 Correct 69 ms 21752 KB Output is correct
7 Correct 69 ms 21496 KB Output is correct
8 Correct 99 ms 31352 KB Output is correct
9 Correct 15 ms 4348 KB Output is correct
10 Correct 156 ms 44280 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 107168 KB Output is correct
2 Correct 131 ms 49784 KB Output is correct
3 Runtime error 152 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 107168 KB Output is correct
2 Correct 131 ms 49784 KB Output is correct
3 Runtime error 152 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 107168 KB Output is correct
2 Correct 131 ms 49784 KB Output is correct
3 Runtime error 152 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 764 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 6 ms 888 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 888 KB Output is correct
10 Correct 5 ms 1144 KB Output is correct
11 Correct 5 ms 1144 KB Output is correct
12 Correct 5 ms 1144 KB Output is correct
13 Correct 6 ms 1144 KB Output is correct
14 Correct 6 ms 1144 KB Output is correct
15 Correct 6 ms 1144 KB Output is correct

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1784 KB Output is correct
2 Correct 128 ms 38108 KB Output is correct
3 Correct 7 ms 2040 KB Output is correct
4 Correct 8 ms 4856 KB Output is correct
5 Correct 6 ms 2168 KB Output is correct
6 Correct 37 ms 13048 KB Output is correct
7 Correct 7 ms 1656 KB Output is correct
8 Correct 15 ms 5112 KB Output is correct
9 Correct 70 ms 22648 KB Output is correct
10 Correct 161 ms 44280 KB Output is correct
11 Correct 6 ms 1016 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 37 ms 11000 KB Output is correct
14 Correct 7 ms 1144 KB Output is correct
15 Correct 15 ms 3832 KB Output is correct
16 Correct 69 ms 21752 KB Output is correct
17 Correct 69 ms 21496 KB Output is correct
18 Correct 99 ms 31352 KB Output is correct
19 Correct 15 ms 4348 KB Output is correct
20 Correct 156 ms 44280 KB Output is correct
21 Correct 334 ms 107168 KB Output is correct
22 Correct 131 ms 49784 KB Output is correct
23 Runtime error 152 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -