oj.uz

Submission #506070

# Submission time Handle Problem Language Result Execution time Memory
506070 2022-01-11T13:28:55 Z amukkalir Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 87 ms 15948 KB 
#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
typedef unsigned long long ull; 

#define pii pair<ll,ll> 
#define se second 
#define fi first
#define pb push_back 
#define wek puts("wekwek")
#define wik puts("-------")

const int nax = 2e3; 
const ll INF = (1ll<<42)-1; 
int n, a, b; 
int dp[nax+5][nax+5]; 
ll p[nax+5];

ll sum (int l, int r) {
    return p[r] - p[l-1]; 
}

int f(int grup, int idx, ll x) {
    if(grup > b) return 0; 
    if(idx == n+1) {
        return (a <= grup && grup <= b); 
    }

    int &ret = dp[grup][idx]; 
    if(~ret) return ret; 

	ret = 0; 
    for(int j=idx; j<=n; j++) {
        if((x | sum(idx,j)) == x) {
			ret |= f(grup+1, j+1, x); 
		}
    }
	//cout << grup << " " << idx << " " << ret << endl; 
    return ret; 
}

signed main () {	
    scanf("%d %d %d", &n, &a, &b);
    for(int i=1; i<=n; i++)  {
        scanf("%lld", &p[i]); 
        p[i] += p[i-1]; 
		cout << i << " " << p[i] << endl; 
    }

    ll lo = 0, hi = INF; 
    ll ans = hi; 
    while(lo <= hi) {
        ll mid = (lo+hi)/2; 
        memset(dp, -1, sizeof dp); 
		//cout << bitset<64> (mid) << endl; 
        if(f(0, 1, mid)) {
            ans = mid; 
            hi = mid-1; 
        } else {
            lo = mid+1; 
        }
    }

    printf("%lld", ans); 
}

/*

*/

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d %d %d", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%lld", &p[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 15948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 15888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 15916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 15948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 15948 KB Output isn't correct
2 Halted 0 ms 0 KB -