Submission #70488136

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=(a);i<(n);i++)
#define per(i,a,n) for (int i=(n)-1;i>=(a);i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

bitset<125000> d[555];
const int N=500;
const int inf=1<<30;
int dp[2222][2222],p1[201000];
int n,b[201000],nv[201000];
void chkmin(int &a,int b) {
	a=min(a,b);
}
void solve() {
	scanf("%d",&n);
	int s1=0,s0=0;
	int m=n*(n-1)/2;
	rep(i,0,m) {
		scanf("%d",&b[i]);
		if (b[i]==1) p1[s1]=i,s1++;
		else s0++;
	}
	int nxt=-1;
	per(i,0,m+1) {
		if (d[n].test(i)) nxt=i;
		nv[i]=nxt;
		//printf("!! %d %d\n",i,nxt);
	}
	rep(i,0,m+1) rep(j,0,s1+1) dp[i][j]=inf;
	dp[0][0]=0;
	rep(i,0,m) rep(j,0,min(s1,i)+1) if (dp[i][j]<inf) {
		// 1
		if (j+1<=s1&&nv[j+1]+s0-(i-j)<=m) {
			chkmin(dp[i+1][j+1],dp[i][j]+abs(i-p1[j]));
		}
		// 0
		chkmin(dp[i+1][j],dp[i][j]);
	}
	int ans=dp[m][s1];
	printf("%d\n",ans);
}
int _;
int main() {
	d[0].set(0);
	for (int j=0;j<=N;j++) {
		for (int k=1;j+k<=N;k++) {
			d[j+k]|=d[j]<<(k*(k-1)/2);
		}
	}
	for (scanf("%d",&_);_;_--) {
		solve();
	}
}

Submission Info

Submission Time
Task D - Valid Output for DSU Problems
User apiad
Language C++ 20 (gcc 12.2)
Score 0
Code Size 1639 Byte
Status RE
Exec Time 522 ms
Memory 32780 KiB

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:33:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:37:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |                 scanf("%d",&b[i]);
      |                 ~~~~~^~~~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:68:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |         for (scanf("%d",&_);_;_--) {
      |              ~~~~~^~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 1
AC × 2
WA × 40
RE × 50
Set Name Test Cases
Sample sample.txt
All maxB.txt, maxN_1.txt, maxN_10.txt, maxN_11.txt, maxN_12.txt, maxN_13.txt, maxN_14.txt, maxN_15.txt, maxN_16.txt, maxN_17.txt, maxN_18.txt, maxN_19.txt, maxN_2.txt, maxN_20.txt, maxN_3.txt, maxN_4.txt, maxN_5.txt, maxN_6.txt, maxN_7.txt, maxN_8.txt, maxN_9.txt, middle_1.txt, middle_10.txt, middle_11.txt, middle_12.txt, middle_13.txt, middle_14.txt, middle_15.txt, middle_16.txt, middle_17.txt, middle_18.txt, middle_19.txt, middle_2.txt, middle_20.txt, middle_21.txt, middle_22.txt, middle_23.txt, middle_24.txt, middle_25.txt, middle_26.txt, middle_27.txt, middle_28.txt, middle_29.txt, middle_3.txt, middle_30.txt, middle_4.txt, middle_5.txt, middle_6.txt, middle_7.txt, middle_8.txt, middle_9.txt, random_1.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_2.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_3.txt, random_30.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample.txt, small_1.txt, small_10.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, small_8.txt, small_9.txt
Case Name Status Exec Time Memory
maxB.txt AC 290 ms 11412 KiB
maxN_1.txt RE 439 ms 32736 KiB
maxN_10.txt RE 432 ms 32696 KiB
maxN_11.txt RE 431 ms 32596 KiB
maxN_12.txt RE 445 ms 32644 KiB
maxN_13.txt RE 439 ms 32780 KiB
maxN_14.txt RE 439 ms 32656 KiB
maxN_15.txt RE 435 ms 32728 KiB
maxN_16.txt RE 444 ms 32628 KiB
maxN_17.txt RE 390 ms 32416 KiB
maxN_18.txt RE 437 ms 32616 KiB
maxN_19.txt RE 435 ms 32600 KiB
maxN_2.txt RE 434 ms 32660 KiB
maxN_20.txt RE 438 ms 32664 KiB
maxN_3.txt RE 440 ms 32708 KiB
maxN_4.txt RE 435 ms 32564 KiB
maxN_5.txt RE 391 ms 32460 KiB
maxN_6.txt RE 437 ms 32712 KiB
maxN_7.txt RE 433 ms 32632 KiB
maxN_8.txt RE 391 ms 32404 KiB
maxN_9.txt RE 390 ms 32500 KiB
middle_1.txt WA 511 ms 21620 KiB
middle_10.txt WA 522 ms 21484 KiB
middle_11.txt WA 502 ms 21980 KiB
middle_12.txt WA 502 ms 21668 KiB
middle_13.txt WA 508 ms 21804 KiB
middle_14.txt WA 501 ms 21536 KiB
middle_15.txt WA 514 ms 21896 KiB
middle_16.txt WA 511 ms 22112 KiB
middle_17.txt WA 513 ms 22200 KiB
middle_18.txt WA 509 ms 21680 KiB
middle_19.txt WA 509 ms 21504 KiB
middle_2.txt WA 506 ms 21720 KiB
middle_20.txt WA 503 ms 21836 KiB
middle_21.txt WA 506 ms 21660 KiB
middle_22.txt WA 504 ms 21092 KiB
middle_23.txt WA 508 ms 21664 KiB
middle_24.txt WA 504 ms 22048 KiB
middle_25.txt WA 503 ms 21972 KiB
middle_26.txt WA 503 ms 21960 KiB
middle_27.txt WA 510 ms 22176 KiB
middle_28.txt WA 504 ms 21300 KiB
middle_29.txt WA 508 ms 21868 KiB
middle_3.txt WA 512 ms 21608 KiB
middle_30.txt WA 520 ms 21540 KiB
middle_4.txt WA 515 ms 22164 KiB
middle_5.txt WA 506 ms 21588 KiB
middle_6.txt WA 508 ms 21480 KiB
middle_7.txt WA 498 ms 21472 KiB
middle_8.txt WA 513 ms 21864 KiB
middle_9.txt WA 495 ms 21240 KiB
random_1.txt RE 407 ms 32272 KiB
random_10.txt RE 334 ms 31280 KiB
random_11.txt RE 395 ms 32120 KiB
random_12.txt RE 337 ms 31480 KiB
random_13.txt RE 383 ms 32016 KiB
random_14.txt RE 341 ms 31496 KiB
random_15.txt RE 424 ms 32708 KiB
random_16.txt RE 325 ms 31300 KiB
random_17.txt RE 326 ms 31372 KiB
random_18.txt RE 406 ms 32328 KiB
random_19.txt RE 335 ms 31484 KiB
random_2.txt RE 360 ms 31848 KiB
random_20.txt RE 359 ms 31728 KiB
random_21.txt RE 327 ms 31308 KiB
random_22.txt RE 331 ms 31364 KiB
random_23.txt RE 321 ms 31260 KiB
random_24.txt RE 335 ms 31480 KiB
random_25.txt RE 378 ms 31976 KiB
random_26.txt RE 339 ms 31492 KiB
random_27.txt RE 371 ms 31868 KiB
random_28.txt RE 371 ms 31816 KiB
random_29.txt RE 386 ms 32104 KiB
random_3.txt RE 377 ms 31932 KiB
random_30.txt RE 361 ms 31760 KiB
random_4.txt RE 366 ms 32084 KiB
random_5.txt RE 351 ms 31624 KiB
random_6.txt RE 328 ms 31220 KiB
random_7.txt RE 326 ms 31364 KiB
random_8.txt RE 331 ms 31384 KiB
random_9.txt RE 353 ms 31628 KiB
sample.txt AC 242 ms 11460 KiB
small_1.txt WA 266 ms 11652 KiB
small_10.txt WA 256 ms 11692 KiB
small_2.txt WA 265 ms 11648 KiB
small_3.txt WA 265 ms 11484 KiB
small_4.txt WA 265 ms 11476 KiB
small_5.txt WA 264 ms 11372 KiB
small_6.txt WA 265 ms 11532 KiB
small_7.txt WA 264 ms 11652 KiB
small_8.txt WA 265 ms 11460 KiB
small_9.txt WA 266 ms 11716 KiB