Submission #1028909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028909		elotelo966	Netrpeljivost (COI23_netrpeljivost)	C++17	100 / 100	649 ms	107280 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define mod 998244353
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 2050
#define fi first
#define se second

int n;
int dizi[lim][lim];
int dp[lim][lim];

inline pair<int,int> find(int cur,int x){
	int tut,cev=0;
	for(int i=31;i>=0;i--){
		if((cur&(1ll<<i))!=((cur+1)&(1ll<<i))){
			tut=i;
			cev+=(x&(1ll<<i))?0:(1ll<<i);
			break;
		}
		else cev+=(x&(1ll<<i))?(1ll<<i):0;
	}
	//cout<<cur<<" "<<x<<" "<<tut<<endl;
	return {cev,cev+(1ll<<tut)};
}

inline int f(int sira,int eleman){
	if(sira==n)return 0;
	if(~dp[sira][eleman])return dp[sira][eleman];
	int cev=LLONG_MAX;
	pair<int,int> ara=find(sira,eleman);
	//cout<<sira<<" "<<eleman<<" "<<ara.fi<<" "<<ara.se<<endl;
	for(int i=ara.fi;i<ara.se;i++){
		cev=min(cev,f(sira+1,i)+(f(sira+1,i)==LLONG_MAX?0:dizi[eleman][i]));
	}
	return dp[sira][eleman]=cev;
}

int32_t main(){
	faster
	cin>>n;
	memset(dp,-1,sizeof(dp));
	FOR{
		for(int j=1;j<=n;j++){
			cin>>dizi[i-1][j-1];
		}
	}
	
	int cev=LLONG_MAX;
	
	FOR{
		cev=min(cev,f(0,i-1));
	}
	
	cout<<cev<<'\n';
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int _Z1fxx.part.0(long long int, long long int)':
Main.cpp:31:22: warning: 'tut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  return {cev,cev+(1ll<<tut)};
      |                  ~~~~^~~~~~
Main.cpp:21:6: note: 'tut' was declared here
   21 |  int tut,cev=0;
      |      ^~~
Main.cpp:31:22: warning: 'tut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  return {cev,cev+(1ll<<tut)};
      |                  ~~~~^~~~~~
Main.cpp:21:6: note: 'tut' was declared here
   21 |  int tut,cev=0;
      |      ^~~
Main.cpp:31:22: warning: 'tut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  return {cev,cev+(1ll<<tut)};
      |                  ~~~~^~~~~~
Main.cpp:21:6: note: 'tut' was declared here
   21 |  int tut,cev=0;
      |      ^~~
Main.cpp:31:22: warning: 'tut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  return {cev,cev+(1ll<<tut)};
      |                  ~~~~^~~~~~
Main.cpp:21:6: note: 'tut' was declared here
   21 |  int tut,cev=0;
      |      ^~~
Main.cpp:31:22: warning: 'tut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  return {cev,cev+(1ll<<tut)};
      |                  ~~~~^~~~~~
Main.cpp:21:6: note: 'tut' was declared here
   21 |  int tut,cev=0;
      |      ^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:31:22: warning: 'tut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  return {cev,cev+(1ll<<tut)};
      |                  ~~~~^~~~~~
Main.cpp:21:6: note: 'tut' was declared here
   21 |  int tut,cev=0;
      |      ^~~
Main.cpp:31:22: warning: 'tut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  return {cev,cev+(1ll<<tut)};
      |                  ~~~~^~~~~~
Main.cpp:21:6: note: 'tut' was declared here
   21 |  int tut,cev=0;
      |      ^~~
Main.cpp:31:22: warning: 'tut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  return {cev,cev+(1ll<<tut)};
      |                  ~~~~^~~~~~
Main.cpp:21:6: note: 'tut' was declared here
   21 |  int tut,cev=0;
      |      ^~~

• Subtask 1: 10 / 10
• Subtask 2: 17 / 17
• Subtask 3: 32 / 32
• Subtask 4: 41 / 41