Submission #117219

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define pb push_back
#define mp make_pair
typedef long long ll;
const int inf = (1<<28);

int main() {
  int n; cin >> n;
  
  if(n == 2) { cout << "0 0" << endl; return 0; }
  
  vector<vector<ll> > adj(n, vector<ll>(n));
  rep(i, n) adj[i][i] = inf;
  rep(i, n-1) rep(j, n-1-i) {
    int e; cin >> e;
    adj[i][i+j+1] = adj[i+j+1][i] = e;
  }
  
  vector<vector<ll> > dp(n, vector<ll>(1<<n, inf));
  dp[0][1] = 0;
  
  rep(j, 1<<n) rep(i, n) {
    if(!(j & (1<<i))) continue;
    rep(k, n) {
      if(j & (1<<k)) continue;
      dp[k][j|(1<<k)] = min(dp[k][j|(1<<k)],
                            dp[i][j] + adj[i][k]);
    }
  }
  
  ll mini = inf;
  rep(i, n) mini = min(mini, dp[i][(1<<n)-1]+adj[i][0]);
  cout << n << " " << mini << endl;
}

Submission Info

Submission Time
Task A - 特別作戦
User suminos
Language C++ (G++ 4.6.4)
Score 100
Code Size 1009 Byte
Status AC
Exec Time 53 ms
Memory 5016 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 24
Set Name Test Cases
All 00-sample, 01-maximum, 02-minimum, 03-flat, 50-random-00, 50-random-01, 50-random-02, 50-random-03, 50-random-04, 50-random-05, 50-random-06, 50-random-07, 50-random-08, 50-random-09, 50-random-10, 50-random-11, 50-random-12, 50-random-13, 50-random-14, 50-random-15, 50-random-16, 50-random-17, 50-random-18, 50-random-19
Case Name Status Exec Time Memory
00-sample AC 21 ms 924 KiB
01-maximum AC 53 ms 4896 KiB
02-minimum AC 22 ms 792 KiB
03-flat AC 51 ms 5016 KiB
50-random-00 AC 23 ms 800 KiB
50-random-01 AC 22 ms 916 KiB
50-random-02 AC 23 ms 792 KiB
50-random-03 AC 21 ms 916 KiB
50-random-04 AC 21 ms 924 KiB
50-random-05 AC 22 ms 796 KiB
50-random-06 AC 27 ms 1640 KiB
50-random-07 AC 21 ms 804 KiB
50-random-08 AC 36 ms 2720 KiB
50-random-09 AC 53 ms 4908 KiB
50-random-10 AC 24 ms 852 KiB
50-random-11 AC 35 ms 2728 KiB
50-random-12 AC 21 ms 804 KiB
50-random-13 AC 23 ms 788 KiB
50-random-14 AC 27 ms 1580 KiB
50-random-15 AC 22 ms 920 KiB
50-random-16 AC 21 ms 920 KiB
50-random-17 AC 29 ms 1688 KiB
50-random-18 AC 35 ms 2840 KiB
50-random-19 AC 21 ms 920 KiB