oj.uz

Submission #81773

# Submission time Handle Problem Language Result Execution time Memory
81773 2018-10-26T13:48:13 Z Bodo171 Skyscraper (JOI16_skyscraper) C++14
15 / 100
 7 ms 1308 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=105;
const long long mod=1000*1000*1000+7;
long long dp[2][nmax][nmax*10][2][2];
int a[nmax];
int n,l,use,cost,newcost,st,dr;
long long i,gaps,difs,endss;
long long ans;
void prp(long long &a,long long b)
{
    a+=(b%mod);
    if(a>=mod)
        a-=mod;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>l;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    //dp[use][cc][cost][fix_st][fix_dr]
    for(st=0;st<2;st++)
        for(dr=0;dr<2;dr++)
           dp[1][1][0][st][dr]=1;
    for(int cnt=2;cnt<=n;cnt++)
    {
        use=1-use;
        for(i=1;i<=n;i++)
          for(cost=0;cost<=l;cost++)
            for(st=0;st<2;st++)
              for(dr=0;dr<2;dr++)
               dp[1-use][i][cost][st][dr]=0;
        for(i=1;i<=n;i++)
          for(cost=0;cost<=l;cost++)
            for(st=0;st<2;st++)
              for(dr=0;dr<2;dr++)
        {
             gaps=i+1-st-dr;
             endss=2*(i-1)+(1-st)+(1-dr);
             newcost=(a[cnt]-a[cnt-1])*endss+cost;
             if(cost<=l)
             {
                 prp(dp[1-use][i-1][newcost][st][dr],1LL*dp[use][i][cost][st][dr]*(i-1));
                 prp(dp[1-use][i+1][newcost][st][dr],1LL*dp[use][i][cost][st][dr]*gaps);
                 prp(dp[1-use][i][newcost][st][dr],1LL*dp[use][i][cost][st][dr]*endss);
                 if(!st)
                 {
                     prp(dp[1-use][i+1][newcost][1][dr],dp[use][i][cost][st][dr]);
                     prp(dp[1-use][i][newcost][1][dr],dp[use][i][cost][st][dr]);
                 }
                 if(!dr)
                 {
                     prp(dp[1-use][i+1][newcost][st][1],dp[use][i][cost][st][dr]);
                     prp(dp[1-use][i][newcost][st][1],dp[use][i][cost][st][dr]);
                 }
             }
        }
    }
    use=1-use;
    for(i=0;i<=l;i++)
        prp(ans,dp[use][1][i][1][1]);
    cout<<ans;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Incorrect 7 ms 1308 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1308 KB Output is correct
2 Correct 4 ms 1308 KB Output is correct
3 Correct 3 ms 1308 KB Output is correct
4 Correct 4 ms 1308 KB Output is correct
5 Correct 4 ms 1308 KB Output is correct
6 Correct 3 ms 1308 KB Output is correct
7 Correct 3 ms 1308 KB Output is correct
8 Correct 3 ms 1308 KB Output is correct
9 Correct 3 ms 1308 KB Output is correct
10 Correct 3 ms 1308 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Incorrect 7 ms 1308 KB Output isn't correct
6 Halted 0 ms 0 KB -