oj.uz

Submission #95023

# Submission time Handle Problem Language Result Execution time Memory
95023 2019-01-26T22:12:39 Z Rouge_Hugo Kronican (COCI16_kronican) C++14
80 / 100
 65 ms 8312 KB 
#include <bits/stdc++.h>
using namespace std;
int n,k;
int d[1000009];
int a[22][22];	
int dp(int mask,int y)
{
	if (y==k)return 0;
	if(d[mask]!=-1)return d[mask];
	int mn=10000000000;
	int u=10000000000;
	for(int i=0;i<n;i++)
	{
		int l=21;
		mn=10000000000;
		if (((1<<i)&mask)==(1<<i))
		{
			for(int j=0;j<n;j++)
			{
				if (i!=j&&(((1<<j)&mask)==(1<<j)))
				{
					mn=min(mn,a[i][j]);
				}
			}
			u=min(u,dp(mask-(1<<i),y-1)+mn);
		}
	}
	return d[mask]=u;
}
int main()
{ios_base::sync_with_stdio(false);
cin.tie(NULL);

	memset (d,-1,sizeof d);
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>a[i][j];
		}
	}
	cout<<dp((1<<n)-1,n);
}

Compilation message

kronican.cpp: In function 'int dp(int, int)':
kronican.cpp:10:9: warning: overflow in implicit constant conversion [-Woverflow]
  int mn=10000000000;
         ^~~~~~~~~~~
kronican.cpp:11:8: warning: overflow in implicit constant conversion [-Woverflow]
  int u=10000000000;
        ^~~~~~~~~~~
kronican.cpp:15:6: warning: overflow in implicit constant conversion [-Woverflow]
   mn=10000000000;
      ^~~~~~~~~~~
kronican.cpp:14:7: warning: unused variable 'l' [-Wunused-variable]
   int l=21;
       ^

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 5 ms 4216 KB Output is correct
4 Correct 5 ms 4216 KB Output is correct
5 Correct 10 ms 4216 KB Output is correct
6 Correct 18 ms 4216 KB Output is correct
7 Correct 31 ms 4216 KB Output is correct
8 Correct 65 ms 4376 KB Output is correct
9 Runtime error 10 ms 8312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 10 ms 8312 KB Execution killed with signal 11 (could be triggered by violating memory limits)