oj.uz

Submission #269427

# Submission time Handle Problem Language Result Execution time Memory
269427 2020-08-17T07:04:32 Z 최은수(#5097) Ruins 3 (JOI20_ruins3) C++17
6 / 100
 1288 ms 138492 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mod=inf;
inline int add(int x,int y)
{
    return x+y<mod?x+y:x+y-mod;
}
inline int mul(int x,int y)
{
    return(int)((ll)x*y%mod);
}
inline vector<int>tri(int x,int n)
{
    vector<int>ret;
    for(int i=0;i<n;i++)
        ret.eb(x%3),x/=3;
    return ret;
}
inline int sum(int x)
{
    int ret=0;
    while(x!=0)
        ret+=x%3,x/=3;
    return ret;
}
inline int tri(vector<int>v)
{
    int ret=0;
    for(int i=0,c=1;i<(int)v.size();i++,c*=3)
        ret+=v[i]*c;
    return ret;
}
bool chk[1234];
vector<int>lv[30];
int dp[1600000];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int v;
        cin>>v;
        chk[v]=1;
    }
    int n3=1;
    for(int i=0;i<n;i++)
        n3*=3;
    for(int i=0;i<n3;i++)
        lv[sum(i)].eb(i);
    dp[0]=1;
    for(int i=0;i<n*2;i++)
    {
        for(int&t:lv[i])
        {
            vector<int>v=tri(t,n);
            vector<int>v2=v;
            for(int j=n;j-->1;)
                if(v2[j]>1)
                    v2[j-1]+=v2[j]-1;
            bool f=0;
            for(int j=0;j<n;j++)
            {
                if(v[j]==2)
                    continue;
                f|=v2[j]==0;
                if(chk[n*2-i]&&!f)
                    continue;
                if(!chk[n*2-i]&&f)
                    continue;
                v[j]++;
                int nx=tri(v);
                dp[nx]=add(dp[nx],dp[t]);
                v[j]--;
            }
        }
    }
    cout<<dp[lv[n*2][0]]<<endl;
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1146 ms 13628 KB Output is correct
3 Correct 1030 ms 13580 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 931 ms 13676 KB Output is correct
6 Correct 1065 ms 13708 KB Output is correct
7 Correct 850 ms 13556 KB Output is correct
8 Correct 1288 ms 13628 KB Output is correct
9 Correct 1050 ms 13756 KB Output is correct
10 Correct 1079 ms 13756 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1146 ms 13628 KB Output is correct
3 Correct 1030 ms 13580 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 931 ms 13676 KB Output is correct
6 Correct 1065 ms 13708 KB Output is correct
7 Correct 850 ms 13556 KB Output is correct
8 Correct 1288 ms 13628 KB Output is correct
9 Correct 1050 ms 13756 KB Output is correct
10 Correct 1079 ms 13756 KB Output is correct
11 Runtime error 480 ms 138492 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1146 ms 13628 KB Output is correct
3 Correct 1030 ms 13580 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 931 ms 13676 KB Output is correct
6 Correct 1065 ms 13708 KB Output is correct
7 Correct 850 ms 13556 KB Output is correct
8 Correct 1288 ms 13628 KB Output is correct
9 Correct 1050 ms 13756 KB Output is correct
10 Correct 1079 ms 13756 KB Output is correct
11 Runtime error 480 ms 138492 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -