oj.uz

Submission #417753

# Submission time Handle Problem Language Result Execution time Memory
417753 2021-06-04T08:39:04 Z 조영욱(#7641) Long puzzle (innopolis2021_final_D) C++17
20 / 100
 320 ms 333172 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
int len[20];
int le[20];
int ri[20];
long long dp[20][1048576];
int n,l;

long long ans(int ind,int bit,int ln) {
    if (ri[ind]==1&&ln==l) {
        return dp[ind][bit]=1;
    }
    if (ri[ind]==1) {
        return dp[ind][bit]=0;
    }
    if (dp[ind][bit]!=-1) {
        return dp[ind][bit];
    }
    long long ret=0;
    for(int i=0;i<n;i++) {
        if (bit&(1<<i)) {

        }
        else if (ri[ind]+le[i]==2) {
            ret+=ans(i,bit+(1<<i),ln+len[i]);
        }
    }
    return dp[ind][bit]=ret;
}

int main(void) {
    scanf("%d %d",&n,&l);
    for(int i=0;i<n;i++) {
        char str1[7];
        char str2[7];
        scanf("%d %s %s",&len[i],str1,str2);
        if (strcmp(str1,"in")==0) {
            le[i]=0;
        }
        else if (strcmp(str1,"none")==0) {
            le[i]=1;
        }
        else {
            le[i]=2;
        }
        if (strcmp(str2,"in")==0) {
            ri[i]=0;
        }
        else if (strcmp(str2,"none")==0) {
            ri[i]=1;
        }
        else {
            ri[i]=2;
        }
    }
    memset(dp,-1,sizeof(dp));
    long long ret=0;
    for(int i=0;i<n;i++) {
        if (le[i]==1) {
            ans(i,(1<<i),len[i]);
        }
    }

    for(int i=0;i<(1<<n);i++) {
            bool flag=false;
        for(int j=0;j<n;j++) {
            if (ri[j]==1&&dp[j][i]>0) {
                flag=true;
            }
        }
        if (flag)
            ret++;
    }
    printf("%lld",ret);
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 164420 KB Output is correct
2 Correct 111 ms 164428 KB Output is correct
3 Correct 305 ms 164424 KB Output is correct
4 Correct 103 ms 164420 KB Output is correct
5 Correct 118 ms 164400 KB Output is correct
6 Correct 102 ms 164312 KB Output is correct
7 Correct 125 ms 164420 KB Output is correct
8 Correct 119 ms 164432 KB Output is correct
9 Correct 105 ms 164428 KB Output is correct
10 Correct 112 ms 164336 KB Output is correct
11 Correct 108 ms 164400 KB Output is correct
12 Correct 144 ms 164368 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 320 ms 333136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 299 ms 333172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 299 ms 333172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 164420 KB Output is correct
2 Correct 111 ms 164428 KB Output is correct
3 Correct 305 ms 164424 KB Output is correct
4 Correct 103 ms 164420 KB Output is correct
5 Correct 118 ms 164400 KB Output is correct
6 Correct 102 ms 164312 KB Output is correct
7 Correct 125 ms 164420 KB Output is correct
8 Correct 119 ms 164432 KB Output is correct
9 Correct 105 ms 164428 KB Output is correct
10 Correct 112 ms 164336 KB Output is correct
11 Correct 108 ms 164400 KB Output is correct
12 Correct 144 ms 164368 KB Output is correct
13 Runtime error 320 ms 333136 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -