oj.uz

Submission #309861

# Submission time Handle Problem Language Result Execution time Memory
309861 2020-10-04T17:49:07 Z Kripton Watching (JOI13_watching) C++14
100 / 100
 392 ms 27064 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int n,p,q;
vector <int> vec[2001];
int v[2001];
int dp[2001][2001];// dp[i][j]=nr minim de garduri MARI ca sa acopere primele i puncte, folosind si j garduri MICI
int where_to(int start,int mar)
{
    int r=start,pas=1<<10;
    while(pas)
    {
        if(r+pas<=n&&v[r+pas]-v[start]+1<=mar)
            r+=pas;
        pas/=2;
    }
    return r;
}
bool verif(int w)
{
    int i,j;
    for(i=1; i<=n; i++)
        vec[i].clear();
    for(i=1; i<=n; i++)
        for(j=0; j<=n; j++)
            dp[i][j]=INT_MAX;
    int x=where_to(1,w),y=where_to(1,2*w);
    vec[x].push_back(1);
    dp[x][1]=0;
    vec[y].push_back(0);
    dp[y][0]=1;
    for(i=1; i<n; i++)
    {
        x=where_to(i+1,w);
        y=where_to(i+1,2*w);
        for(j=0; j<vec[i].size(); j++)
        {
            if(x!=i&&vec[i][j]+1<=p&&dp[i][vec[i][j]]<dp[x][vec[i][j]+1])
            {
                if(dp[x][vec[i][j]+1]==INT_MAX)
                    vec[x].push_back(vec[i][j]+1);
                dp[x][vec[i][j]+1]=dp[i][vec[i][j]];
            }
            if(y!=i&&dp[i][vec[i][j]]+1<dp[y][vec[i][j]])
            {
                if(dp[y][vec[i][j]]==INT_MAX)
                    vec[y].push_back(vec[i][j]);
                dp[y][vec[i][j]]=dp[i][vec[i][j]]+1;
            }
        }
    }
    for(i=0;i<vec[n].size();i++)
        if(dp[n][vec[n][i]]<=q)
            break;
    if(i==vec[n].size())
        return 0;
    return 1;
}
int cautbin()
{
    int r=0,pas=1<<30;
    while(pas)
    {
        if(!verif(r+pas))
            r+=pas;
        pas/=2;
    }
    return r+1;
}
int main()
{
#ifdef HOME
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>p>>q;
    if(p+q>=n)
    {
        cout<<1;
        return 0;
    }
    for(int i=1; i<=n; i++)
        cin>>v[i];
    sort(v+1,v+n+1);
    cout<<cautbin();
    return 0;
}

Compilation message

watching.cpp: In function 'bool verif(int)':
watching.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(j=0; j<vec[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
watching.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(i=0;i<vec[n].size();i++)
      |             ~^~~~~~~~~~~~~~
watching.cpp:55:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     if(i==vec[n].size())
      |        ~^~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1 ms 896 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 2 ms 896 KB Output is correct
12 Correct 2 ms 896 KB Output is correct
13 Correct 1 ms 896 KB Output is correct
14 Correct 1 ms 896 KB Output is correct
15 Correct 1 ms 896 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 16128 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 72 ms 16128 KB Output is correct
8 Correct 104 ms 16760 KB Output is correct
9 Correct 185 ms 19704 KB Output is correct
10 Correct 392 ms 27064 KB Output is correct
11 Correct 111 ms 17144 KB Output is correct
12 Correct 317 ms 22776 KB Output is correct
13 Correct 72 ms 16128 KB Output is correct
14 Correct 73 ms 16248 KB Output is correct
15 Correct 72 ms 16128 KB Output is correct