oj.uz

답안 #557664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557664 2022-05-05T18:01:00 Z n0sk1ll 구경하기 (JOI13_watching) C++14
50 / 100
 36 ms 1364 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define erase_uni(x) x.erase(unique(all(x)),x.end())
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;

/*using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;*/







//Note to self: Check for overflow

int a[2005];
bool dp[103][103][103];

bool moze(int w, int n, int p, int q)
{
    int pp=0,qq=0;
    dp[0][0][0]=1;
    fff(i,1,n) fff(j,0,p) fff(k,0,q) dp[i][j][k]=0;
    fff(i,1,n)
    {
        while (a[i]-a[pp+1]+1>w) ++pp;
        while (a[i]-a[qq+1]+1>2*w) ++qq;
        fff(j,0,p) fff(k,0,q)
        {
            if (j!=0) dp[i][j][k]|=dp[pp][j-1][k];
            if (k!=0) dp[i][j][k]|=dp[qq][j][k-1];
        }
    }
    fff(i,0,p) fff(j,0,q) if (dp[n][i][j]) return true;
    return false;
}

int main()
{
    FAST;

    int n,p,q; cin>>n>>p>>q;
    if (p>n) p=n; if (q>n) q=n;
    fff(i,1,n) cin>>a[i];
    sort(a+1,a+n+1);

    int l=0,r=1e9;
    while (r-l>1)
    {
        int mid=(l+r)/2;
        if (moze(mid,n,p,q)) r=mid;
        else l=mid;
    }

    cout<<r<<"\n";
}

//Note to self: Check for overflow

Compilation message

watching.cpp: In function 'bool moze(int, int, int, int)':
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:54:5: note: in expansion of macro 'fff'
   54 |     fff(i,1,n) fff(j,0,p) fff(k,0,q) dp[i][j][k]=0;
      |     ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:54:16: note: in expansion of macro 'fff'
   54 |     fff(i,1,n) fff(j,0,p) fff(k,0,q) dp[i][j][k]=0;
      |                ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:54:27: note: in expansion of macro 'fff'
   54 |     fff(i,1,n) fff(j,0,p) fff(k,0,q) dp[i][j][k]=0;
      |                           ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:55:5: note: in expansion of macro 'fff'
   55 |     fff(i,1,n)
      |     ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:59:9: note: in expansion of macro 'fff'
   59 |         fff(j,0,p) fff(k,0,q)
      |         ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:59:20: note: in expansion of macro 'fff'
   59 |         fff(j,0,p) fff(k,0,q)
      |                    ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:65:5: note: in expansion of macro 'fff'
   65 |     fff(i,0,p) fff(j,0,q) if (dp[n][i][j]) return true;
      |     ^~~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:65:16: note: in expansion of macro 'fff'
   65 |     fff(i,0,p) fff(j,0,q) if (dp[n][i][j]) return true;
      |                ^~~
watching.cpp: In function 'int main()':
watching.cpp:74:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   74 |     if (p>n) p=n; if (q>n) q=n;
      |     ^~
watching.cpp:74:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   74 |     if (p>n) p=n; if (q>n) q=n;
      |                   ^~
watching.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
watching.cpp:75:5: note: in expansion of macro 'fff'
   75 |     fff(i,1,n) cin>>a[i];
      |     ^~~

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 3 ms 712 KB Output is correct
6 Correct 36 ms 1356 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 6 ms 1236 KB Output is correct
12 Correct 15 ms 1236 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -