oj.uz

Submission #417884

# Submission time Handle Problem Language Result Execution time Memory
417884 2021-06-04T12:58:21 Z 반딧불(#7603) Long puzzle (innopolis2021_final_D) C++17
20 / 100
 327 ms 427096 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

int n, l;
ll DP[302][302][602];
int arr[302]; int a[302], b[302];

ll ans;

int main(){
    scanf("%d %d", &n, &l);
    for(int i=1; i<=n; i++){
        string tStr;
        cin >> arr[i] >> tStr;
        a[i] = (tStr[0] == 'n' ? 0 : tStr[0] == 'i' ? 1 : -1);
        cin >> tStr;
        b[i] = (tStr[0] == 'n' ? 0 : tStr[0] == 'o' ? 1 : -1);

        if(!a[i] && !b[i] && arr[i] == l) ans++;
    }

    DP[0][0][300] = 1;
    for(int i=1; i<=n; i++){
        for(int j=0; j<=l; j++) for(int k=0; k<=600; k++) DP[i][j][k] = DP[i-1][j][k];
        if(!a[i] || !b[i]){
            continue;
        }
        int weight = (a[i] - b[i]) / 2;

        for(int j=0; j+arr[i]<=l; j++){
            for(int k=1; k<=600; k++){
                DP[i][j+arr[i]][k+weight] += DP[i-1][j][k];
                DP[i][j+arr[i]][k+weight] %= MOD;
            }
        }
    }

    for(int i=1; i<=n; i++){
        if(a[i] || !b[i]) continue;
        for(int j=1; j<=n; j++){
            if(!a[j] || b[j] || arr[i]+arr[j]>l) continue;

            int weight = (b[i] - a[j]) / 2;
            ans += DP[n][l-arr[i]-arr[j]][300+weight];
            ans %= MOD;
        }
    }
    printf("%lld", ans);
}

Compilation message

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28756 KB Output is correct
2 Correct 19 ms 28656 KB Output is correct
3 Correct 20 ms 28668 KB Output is correct
4 Correct 18 ms 28728 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Incorrect 1 ms 716 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 426932 KB Output is correct
2 Correct 219 ms 426972 KB Output is correct
3 Correct 262 ms 426972 KB Output is correct
4 Correct 316 ms 426984 KB Output is correct
5 Correct 218 ms 426956 KB Output is correct
6 Correct 10 ms 17740 KB Output is correct
7 Correct 25 ms 45940 KB Output is correct
8 Correct 41 ms 74164 KB Output is correct
9 Correct 309 ms 426996 KB Output is correct
10 Correct 315 ms 426988 KB Output is correct
11 Correct 327 ms 426976 KB Output is correct
12 Correct 309 ms 427012 KB Output is correct
13 Correct 236 ms 427096 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28756 KB Output is correct
2 Correct 19 ms 28656 KB Output is correct
3 Correct 20 ms 28668 KB Output is correct
4 Correct 18 ms 28728 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Incorrect 1 ms 716 KB Output isn't correct
7 Halted 0 ms 0 KB -