oj.uz

Submission #620593

# Submission time Handle Problem Language Result Execution time Memory
620593 2022-08-03T07:30:14 Z 조영욱(#8520) Ruins 3 (JOI20_ruins3) C++17
6 / 100
 476 ms 329380 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
bool arr[26];

int getx(vector<int> v) {
    int ret=0;
    int gop=1;
    for(int i=0;i<v.size();i++) {
        ret+=gop*v[i];
        gop*=3;
    }
    return ret;
}

vector<int> getv(int x) {
    vector<int> v;
    for(int i=0;i<n;i++) {
        v.push_back(x%3);
        x/=3;
    }
    return v;
}

const int mod=1e9+7;

int dp[26][59049*27];
int fp[14];

int ans(int ind,int bit) {
//printf("%d %d\n",ind,bit);
    if (ind==n*2) {
        return 1;
    }
    if (dp[ind][bit]!=-1) {
        return dp[ind][bit];
    }
    vector<int> v=getv(bit);
    long long ret=0;
    if (arr[ind]) {
        int mx=n;
        int sum=0;
        int fr[14];
        for(int i=n-1;i>=0;i--) {
            fr[i]=sum;
            if (sum<n-i) {
                sum+=max(1,v[i]);
            }
            else {
                sum+=v[i];
            }
        }
sum=0;
        for(int i=0;i<n;i++) {
            sum+=v[i];
            if (fr[i]+sum<=mx&&v[i]>0) {
                ret+=ans(ind+1,bit-fp[i]);
ret%=mod;
            }
            mx=max(mx,n-1+sum-i);
        }
        return dp[ind][bit]=ret;
    }
    else {
        int mx=n;
        int sum=0;
        int fr[14];
        for(int i=n-1;i>=0;i--) {
            fr[i]=sum;
            if (sum<n-i) {
                sum+=max(1,v[i]);
            }
            else {
                sum+=v[i];
            }
        }
sum=0;
        for(int i=0;i<n;i++) {
            sum+=v[i];
            if (fr[i]+sum>mx&&v[i]>0) {
                ret+=ans(ind+1,bit-fp[i]);
ret%=mod;
            }
            mx=max(mx,n-1+sum-i);
        }
        return dp[ind][bit]=ret;
    }
}

int main(void ) {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        int x;
        scanf("%d",&x);
        x--;
        arr[x]=true;
    }
    fp[0]=1;
    for(int i=1;i<=n;i++) {
        fp[i]=fp[i-1]*3;
    }
    memset(dp,-1,sizeof(dp));
    printf("%lld",ans(0,fp[n]-1));
}

Compilation message

ruins3.cpp: In function 'int getx(std::vector<int>)':
ruins3.cpp:10:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
ruins3.cpp: In function 'int main()':
ruins3.cpp:104:16: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  104 |     printf("%lld",ans(0,fp[n]-1));
      |             ~~~^  ~~~~~~~~~~~~~~
      |                |     |
      |                |     int
      |                long long int
      |             %d
ruins3.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
ruins3.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 162492 KB Output is correct
2 Correct 85 ms 162468 KB Output is correct
3 Correct 82 ms 162504 KB Output is correct
4 Correct 71 ms 162460 KB Output is correct
5 Correct 66 ms 162420 KB Output is correct
6 Correct 89 ms 162532 KB Output is correct
7 Correct 79 ms 162424 KB Output is correct
8 Correct 476 ms 162524 KB Output is correct
9 Correct 183 ms 162528 KB Output is correct
10 Correct 181 ms 162524 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 162492 KB Output is correct
2 Correct 85 ms 162468 KB Output is correct
3 Correct 82 ms 162504 KB Output is correct
4 Correct 71 ms 162460 KB Output is correct
5 Correct 66 ms 162420 KB Output is correct
6 Correct 89 ms 162532 KB Output is correct
7 Correct 79 ms 162424 KB Output is correct
8 Correct 476 ms 162524 KB Output is correct
9 Correct 183 ms 162528 KB Output is correct
10 Correct 181 ms 162524 KB Output is correct
11 Runtime error 223 ms 329380 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 162492 KB Output is correct
2 Correct 85 ms 162468 KB Output is correct
3 Correct 82 ms 162504 KB Output is correct
4 Correct 71 ms 162460 KB Output is correct
5 Correct 66 ms 162420 KB Output is correct
6 Correct 89 ms 162532 KB Output is correct
7 Correct 79 ms 162424 KB Output is correct
8 Correct 476 ms 162524 KB Output is correct
9 Correct 183 ms 162528 KB Output is correct
10 Correct 181 ms 162524 KB Output is correct
11 Runtime error 223 ms 329380 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -