akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

const int MAX = 100;
const long long INF = 20000000000;

int main() {
	int v, e;
	long long graph[MAX][MAX];

	scanf("%d%d", &v, &e);

	for (int i = 0; i < v; i++) {
		for (int j = 0; j < v; j++) {
			if (i == j)graph[i][j] = 0;
			else graph[i][j] = INF;
		}
	}

	for (int i = 0; i < e; i++) {
		int s, t, d;
		scanf("%d%d%d", &s, &t, &d);
		graph[s][t] = d;
	}

	for (int i = 0; i < v; i++) {
		for (int j = 0; j < v; j++) {
			for (int k = 0; k < v; k++) {
				if (graph[j][i] == INF || graph[i][k] == INF)continue;
				graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k]);
			}
		}
	}

	for (int i = 0; i < v; i++) {
		if (graph[i][i] < 0) {
			printf("NEGATIVE CYCLE\n");
			return 0;
		}
	}

	for (int i = 0; i < v; i++) {
		for (int j = 0; j < v; j++) {	
			if (j)printf(" ");
			if (graph[i][j] == INF)printf("INF");
			else printf("%d", graph[i][j]);
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 3284
import java.util.*;
// warm-up
public class Main {

	static void solve() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), k = n/2, t = 2;
		boolean ok = false;
		while (n-->0) {
			int a = sc.nextInt();
			if (a%4==0) k--;
			else if ((a&1)==0) t--;
			if (t==0) { t=2; k--; }
			if (k==0) { ok = true; break; }
		}
		System.out.println(ok ? "Yes" : "No");
		sc.close();		
	}

	public static void main(String args[]) {
		solve();
	}

}

Measured memory_bytes: 58628
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define nxt "\n"
#define intpair pair<int,int>
using namespace std;
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int pow(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline bool sortinrev(const pair<int,int> &a,const pair<int,int> &b){return (a.first > b.first);} //sort pair in descending order
inline ll gcd(ll a, ll b){if (b == 0) return a;return gcd(b, a%b);}
inline ll lcm(ll a, ll b){return (a*b)/gcd(a, b);}
int main(){
		ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll x,bal=100;
    cin>>x;
    for(int i=1;i<=4000;i++){
			    bal = bal*(1.01);
			    if(bal >= x){
						cout<<i<<endl;
						return 0;
					}
		}
}



Measured memory_bytes: 3648
#include<stdio.h>
int main(){
   int a,b,c;
   scanf("%d %d %d",&a,&b,&c);
   int tmp1=a;
   a=b;
   b=tmp1;
   int tmp2=c;
   c=a;
   a=tmp2;
   
   printf("%d %d %d\n",a,b,c);
   return 0;
}


Measured memory_bytes: 1708
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll dp[66000];

int main() {
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);

	for (;;) {
		dp[0] = 0;
		for (int i = 1; i < 66000; i++) dp[i] = -1;
		
		int n; cin >> n; if (!n) break;

		rep(i, 0, n) {
			int bitmask = 0;

			ll m, l; cin >> m >> l;
			rep(j, 0, m) {
				int s, e; cin >> s >> e;
				s -= 6, e -= 6;
				rep(k, s, e)
					bitmask |= (1 << k);
			}
		
			for (int i = 0; i < 66000; i++) if (dp[i] >= 0 && (i & bitmask) == 0) {
				dp[i | bitmask] = max(dp[i | bitmask], dp[i] + l);
			}
		}

		ll ans = 0;
		for (int i = 0; i < 66000; i++) ans = max(ans, dp[i]);
		cout << ans << endl;
	}
}



Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
template <class T> T input() {T t; cin>>t; return t;}
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define CHMAX(a,b) a = max(a,b)
#define CHMIN(a,b) a = min(a,b)
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define e1 first
#define e2 second
#define newline putchar('\n')
#define cspace ' '
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;
const VI dx = {1, 0, -1, 0};
const VI dy = {0, 1, 0, -1};

VVI s;

int main()
{
    int h, w, k;
    cin>>h>>w>>k;
    s.resize(h, VI(w));
    REP(i,h) REP(j,w) s[i][j] = (int)(input<char>() - '0');
    ll ans = INF;
    REP(i,1<<(h-1)) {
        ll tans = 0;
        VI sep(h);
        int sep_num = 0;
        REP(j,h) {
            sep[j] = sep_num;
            sep_num += (i >> j) & 1;
        }
        sep_num++;
        tans += sep_num - 1;

        VI cnt(sep_num);
        bool out = false;
        //cout<<sep_num<<endl;
        REP(j,w) {
            //cout<<i<<cspace<<j<<endl;

            bool flag = true;
            REP(l,h) {
                cnt[sep[l]] += s[l][j];

                if (cnt[sep[l]] > k) {
                    flag = false;
                    break;
                }
            }

            if (!flag) {
                if (!out) {
                    cnt.assign(sep_num, 0);
                    tans++;
                    j--;
                    out = true;
                    continue;
                } else {
                    tans = INF;
                    break;
                }
            }
            out = false;
        }
        //cout<<i<<":"<<cspace<<tans<<endl;

        CHMIN(ans,tans);
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int main () {
	std::vector<int> v(3);
	int K;
	cin >> v[0] >> v[1] >> v[2] >> K;
	sort(v.begin(), v.end());
	for (int i = 0; i < K; ++i)
	{
		v[2] *= 2;
	}
	cout << v[0] + v[1] + v[2] << endl;

}

Measured memory_bytes: 256
#include <cstdio>

const int kNLmt = 100000;
const int kQLmt = 50000;
const int kBagSize = 10000;

bool binarySearch(int target, int* array, int size) {
  int l = 0, r = size;
  while (l <= r) {
    int mid = (r + l) / 2;
    int x = array[mid];
    if (target == x) {
      return true;
    } else if (x > target) {
      r = mid - 1;
    } else if (x < target) {
      l = mid + 1;
    }
  }
  return false;
}

int main() {
  int n, ns[kNLmt], q, qs[kQLmt], bs = kQLmt / kBagSize,
                                  bag[kBagSize][kQLmt / kBagSize] = {};
  for (int i = 0; i < kBagSize; i++) {
    for (int j = 0; j < bs; j++) {
      bag[i][j] = -1;
    }
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &ns[i]);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) scanf("%d", &qs[i]);

  int cnt = 0;
  for (int i = 0; i < q; i++) {
    bool isInN = binarySearch(qs[i], ns, n);
    if (isInN) {
      int k = qs[i] % kBagSize;
      int nindex = 0;
      bool f = true;
      for (int j = 0; j < bs; j++) {
        if (bag[k][j] == qs[i]) {
          f = false;
          break;
        }
        nindex++;
      }
      if (f) {
        bag[k][nindex] = qs[i];
        cnt++;
      }
    }
  }
  printf("%d\n", cnt);
  return 0;
}



Measured memory_bytes: 3540
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    ll a,b,c;
    cin >> a >> b >> c;

    bool ans = (4*a*b<(c-a-b)*(c-a-b));
    ans = (ans&&(c>a+b));
    cout << ((ans)?"Yes":"No") << endl;
    
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int A, B;
		A = scanner.nextInt();
		B = scanner.nextInt();
		if (B % A == 0){
			System.out.println(A + B);
		}else{
			System.out.println(B - A);
		}
	}
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;

int main() 
{
    int a, b;
    cin >> a >> b;
    int ans = b-a;
    if (b%a == 0) ans = b + a;

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
require 'pp'
$DEBUG ? define_method(:dpp){|e|pp e} : define_method(:dpp){|e|}

# 入力値を数値で返却する
def gets_i()
  gets.chomp.to_i
end
x = gets_i

if x < 100
  puts 0
else
  xc = x.to_s.chars
  a = xc.pop
  b = xc.pop
  m = [b, a].join.to_i
  n = m % 5 == 0 ? m / 5 : m / 5 + 1
  if xc.join.to_i >= n
    puts 1
  else
    puts 0
  end
end

Measured memory_bytes: 14488
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

int main() {
    int         num, E, from, to, table[10000], tmp;
    vector<int> V[10000];
    queue<int>  Q;

    for (int i = 0; i < 10000; i++) table[i] = 0;

    scanf("%d %d", &num, &E);

    for (int i = 0; i < E; i++) {
        scanf("%d %d", &from, &to);
        V[from].push_back(to);
        table[to]++;
    }

    for (int i = 0; i < num; i++) {
        if (table[i] == 0) {
            Q.push(i);
        }
    }

    while (!Q.empty()) {
        tmp = Q.front();
        Q.pop();
        printf("%d\n", tmp);
        for (int i = 0; i < V[tmp].size(); i++) {
            table[V[tmp][i]]--;
            if (table[V[tmp][i]] == 0) {
                Q.push(V[tmp][i]);
            }
        }
    }

    return 0;
}



Measured memory_bytes: 3292
using System;

namespace ReversingNumbers 
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			int n = int.Parse (Console.ReadLine ());
			string[] data = Console.ReadLine ().Split (" ".ToCharArray ());

			//Array.Reverse (data);

			for (n = data.Length-1; n  > -1; n--) {
				if (n != data.Length-1)
					Console.Write (" ");

				Console.Write (data [n]);
			}
			Console.Write ("\n");
		}
	}
}

Measured memory_bytes: 9344
#include<bits/stdc++.h>
using namespace std;
#define MAX 52
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
int H,W;
string s,t;
char A[MAX][MAX];
char B[MAX][MAX];
int asy,asx,aty,atx;
int bsy,bsx,bty,btx;
bool visited[MAX][MAX][MAX][MAX];
struct state{int ay,ax,by,bx;};

string solve(){
  for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
      for(int k=0;k<MAX;k++)
	for(int l=0;l<MAX;l++)
	  visited[i][j][k][l]=false;
  queue<state> Q;
  Q.push((state){asy,asx,bsy,bsx});
  while(!Q.empty()){
    state s=Q.front();Q.pop();
    bool fa=false,fb=false;
    if(s.ay==aty&&s.ax==atx)fa=true;
    if(s.by==bty&&s.bx==btx)fb=true;
    if(fa&&fb)return "Yes";
    if(fa||fb)continue;
    for(int i=0;i<4;i++){
      state to=s;
      to.ay+=dy[i];
      to.ax+=dx[i];
      if(A[to.ay][to.ax]=='#'){
	to.ay=s.ay;
	to.ax=s.ax;
      }
      to.by+=dy[i];
      to.bx-=dx[i];
      if(B[to.by][to.bx]=='#'){
	to.by=s.by;
	to.bx=s.bx;
      }
      if(visited[to.ay][to.ax][to.by][to.bx])continue;
      visited[to.ay][to.ax][to.by][to.bx]=true;
      Q.push(to);
    }
  }
  return "No";
}

int main(){
  while(1){
    cin>>W>>H;
    if(H==0&&W==0)break;
    for(int i=0;i<MAX;i++)
      for(int j=0;j<MAX;j++)
	A[i][j]=B[i][j]='#';
    for(int i=0;i<H;i++){
      cin>>s>>t;
      for(int j=0;j<W;j++){
	A[i+1][j+1]=s[j];
	B[i+1][j+1]=t[j];
	if(s[j]=='L'){
	  A[i+1][j+1]='.';
	  asy=i+1,asx=j+1;
	}
	if(s[j]=='%'){
	  A[i+1][j+1]='.';
	  aty=i+1,atx=j+1;
	}
	if(t[j]=='R'){
	  B[i+1][j+1]='.';
	  bsy=i+1,bsx=j+1;
	}
	if(t[j]=='%'){
	  B[i+1][j+1]='.';
	  bty=i+1,btx=j+1;
	}
      }
    }
    cout<<solve()<<endl;
  }
  return 0;
}

Measured memory_bytes: 9288
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
	int A, B;

	scanf("%d %d", &A, &B);

	if (B * 2 > A)
		printf("0\n");
	else if (B >= A)
		printf("0\n");
	else
		printf("%d", A - B * 2);

	return 0;
}
	

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

int n, m;
char ch[105][105];
int dp[105][105];

int main()
{
	scanf("%d%d", &n, &m);
	rep(i, n) scanf("%s", ch[i]);
	memset(dp, INF, sizeof(dp));
	dp[0][0] = ch[0][0] != '.';
	rep(i, n) rep(j, m) {
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (ch[i][j] != ch[i + 1][j]));
		dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (ch[i][j] != ch[i][j + 1]));
	}
	printf("%d\n", (dp[n - 1][m - 1] + 1) / 2);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C,X;
  cin >>A >>B >>C >>X;
  int i,j,k;
  int count = 0;
  for(i=0;i<=A;i++){
    for(j=0;j<=B;j++){
      for(k=0;k<=C;k++){
        if(500*i+100*j+50*k==X){
          count++;
        }
      }
    }
  }
  cout << count;
}


Measured memory_bytes: 256
import java.util.*;
import java.util.Arrays;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int T = sc.nextInt();
    int A = sc.nextInt();
    int [] a = new int[N];
    double [] temp = new double[N];
    for(int i=0;i<N;i++){
      a[i] = sc.nextInt();
      temp[i] = (double)T-a[i]*0.006;
      
    }
    double min =1000.0;
    int ans = 0;
    double x;
    for(int i=0;i<N;i++){
      x = Math.abs(A-temp[i]);
      if(x<min){
        min = x;
        ans = i+1;
      }
    }
    System.out.println(ans);
  }
}
                          
                         
                    
    
    
    
    
    
    


Measured memory_bytes: 24660
#include <iostream>
#include <vector>

using namespace std;

void compute(vector <int> &A, int n)
{
    for(int i = 1; i < n; i++)
    {
        int current_i = i;

        for(int p = 2; p*p <= current_i; p++)
        {
            while(current_i%p == 0)
            {
                A[p]++; //cout << "e(" << p << ") = " << p << endl;
                current_i /= p;
            }
        }

        if(current_i > 1)
            A[current_i]++;
    }
}

int main()
{
    int n;
    cin >> n;

    vector <int> total_exponent_sum(n + 1, 0);
    compute(total_exponent_sum, n + 1);

    const int LIMIT = 105;
    vector <int> no_of_primes_with_exponent(LIMIT, 0);
    for(int i = 0; i < n + 1; i++)
    {   //cout << i << " " << total_exponent_sum[i] << endl;

        if(total_exponent_sum[i] == 0) continue;
        no_of_primes_with_exponent[total_exponent_sum[i]]++; //cout << " f(" << total_exponent_sum[i] << ") = " << no_of_primes_with_exponent[total_exponent_sum[i]] << endl;
    }

    vector <int> primes_with_exponent_at_least(LIMIT, 0);
    primes_with_exponent_at_least[1] = no_of_primes_with_exponent[1];
    for(int i = LIMIT - 1; i >= 2; i--)
    {
        primes_with_exponent_at_least[i] = primes_with_exponent_at_least[i + 1] + no_of_primes_with_exponent[i];
        //cout << i << " " << primes_with_exponent_at_least[i] << endl;
    }

    int answer = primes_with_exponent_at_least[74];

    answer += primes_with_exponent_at_least[24]*(primes_with_exponent_at_least[2] - 1);
    answer += primes_with_exponent_at_least[14]*(primes_with_exponent_at_least[4] - 1);

    answer +=  (primes_with_exponent_at_least[4]*(primes_with_exponent_at_least[4] - 1)*(primes_with_exponent_at_least[2] - 2))/2;

    cout << answer;
    return 0;
}


Measured memory_bytes: 256
from bisect import bisect_left


def solve(m):
    r = N - 1
    l = 0
    cnt = 0
    while 0 <= r and l < N:
        if A[r] + A[l] < m:
            l += 1
        else:
            cnt += N - l
            r -= 1
    return cnt


N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = S[i] + A[i]

# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = 0
ng = 10 ** 21
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    cnt = solve(mid)
    if cnt >= M:
        ok = mid
    else:
        ng = mid

X = ok
amari = float('inf')
cnt = 0
score = 0
for i, Ai in enumerate(A):
    Aj = X - Ai
    j = bisect_left(A, Aj)
    score += S[N] - S[j] + Ai * (N - j)
    cnt += N - j
    if j < N:
        amari = min(amari, A[i] + A[j])

print(score - (cnt - M) * amari)


Measured memory_bytes: 14492
N, K = map(int, input().split())
A = list(map(int, input().split()))

visited = {1: 0}
index = 0
last = 1

for i in range(K):
    t = A[last - 1]
    index += 1
    if t in visited:
        z = K - i - 1
        l = index - visited[t]
        print([k for k, v in visited.items() if v == visited[t] + (z % l)][0])
        exit()
    else:
        visited[t] = index
        last = t

print(last)



Measured memory_bytes: 32364
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const int INF = -100100100;
typedef pair<int,int> P;

int main(){
    int n;
    cin >> n;
    vector<ll> h(n);
    rep(i,n)cin>>h[i];
    int cnt =0;
    vector<int> tm;
    bool ans = true;
    int prev = -99;
    rep(i,n){
        if(prev <= h[i]-1)prev = h[i]-1;
        else if(prev == h[i]) prev = h[i];
        else{
            ans = false;
        }
    }
    if(ans)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
typedef long long ll;

using namespace std;

int main()
{
	string a,b;
	int ans=0;
	int rt;
	
	cin>>a>>b;
	a += b;
	ans = atoi(a.c_str());
	//cerr<<ans<<endl;
	rt=sqrt(ans);
	if(rt*rt==ans)
	{
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());

		// int[] A = Arrays.stream(sc.nextLine().split("
		// ")).mapToInt(Integer::parseInt).toArray();

		int[] A = new int[N];

		for (int k = 0; k < N; k++) {
			A[k] = Integer.parseInt(sc.next());
		}

		int tmp;
		int i = 0;
		int count = 0;

		boolean flag = true;

		while (flag) {
			flag = false;
			for (int j = N - 1; j > i; j--) {
				if (A[j - 1] > A[j]) {
					tmp = A[j];
					A[j] = A[j - 1];
					A[j - 1] = tmp;
					flag = true;
					count++;
				}	
			}
			i++;
		}

		out_put(A);

		System.out.println(count);

		sc.close();
	}

	private static void out_put(int array[]) {

		System.out.printf("%d", array[0]);

		for (int i = 1; i < array.length; i++) {
			System.out.printf(" %d", array[i]);
		}
		System.out.printf("\n");
	}
}



Measured memory_bytes: 26520
#include <bits/stdc++.h>
using namespace std;
#define pi 3.1415
int main() {
  int N,M,A,sum;
  sum = 0;
  cin >> N >> M;
  for(int i=0;i<M;i++){
    cin >> A;
    sum += A;
  }
  if(N>=sum){
    cout << N - sum << endl;
  }
  else{
    cout << -1 << endl;
  }
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <climits>

constexpr int SINT_MAX = std::numeric_limits<int>::max();
constexpr int SINT_MIN = std::numeric_limits<int>::min();

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

template<class T>
T choose(bool b, T t, T f)
{
    if (b) return t;
    else return f;    
}

const char *YesNo(bool b)
{
    return choose(b, "Yes", "No");
}

const char *YESNO(bool b)
{
    return choose(b, "YES", "NO");
}

template<class NumT>
NumT diffabs(NumT l, NumT r)
{
    if (l < r) return r-l;
    else return l-r;    
}

struct myinout_t {} io;

template<class T>
myinout_t &operator >>(myinout_t &my, T &i)
{
    cin >> i;
    return my;
}

myinout_t &operator >>(myinout_t &my, int &i)
{
    int r = scanf("%d", &i);
    if (r != 1) exit(EXIT_FAILURE);
    return my;
}

myinout_t &operator >>(myinout_t &my, ll &i)
{
    int r = scanf("%lld", &i);
    if (r != 1) exit(EXIT_FAILURE);
    return my;
}

template<class T>
myinout_t &operator <<(myinout_t &my, const T &i)
{
    cout << i;
    return my;
}

myinout_t &operator <<(myinout_t &my, int i)
{
    printf("%d", i);
    return my;
}

myinout_t &operator <<(myinout_t &my, ll i)
{
    printf("%lld", i);
    return my;
}

myinout_t &operator <<(myinout_t &my, double i)
{
    printf("%.20f", i);
    return my;
}

constexpr char BR = '\n';


///////////////////////////////////////////////////
#include <atcoder/dsu>


int main()
{
    int N, Q;
    io >> N >> Q;

    atcoder::dsu ut(N);
    for (int q = 0; q < Q; q++)
    {
        int t, u, v;
        io >> t >> u >> v;
        if (t == 0)
        {
            ut.merge(u, v);
        }
        else
        {
            int s = ut.same(u, v) ? 1 : 0;
            io << s << BR;
        }
        
    }
    
}

Measured memory_bytes: 3976
#include <iostream>
#include <string>
#include <tuple>
#include <algorithm>

int main()
{
  int n;
  scanf("%d", &n);
  using tuple = std::tuple<std::string, int, int>;
  tuple ts[100];
  
  for (int i = 0; i < n; ++i)
  {
    std::string s;
    int p;
    std::cin >> s >> p;
    ts[i] = tuple(s, p, i + 1);
  }
  std::sort(ts, ts + n, [](auto a, auto b)->bool{ if (std::get<0>(a) == std::get<0>(b)) return std::get<1>(a) > std::get<1>(b); else return std::get<0>(a) < std::get<0>(b); });
  for (int i = 0; i < n; ++i)
  {
    printf("%d\n", std::get<2>(ts[i]));
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
vector <int> a,b,c;


void shuffle(int kazu) {
  
  while(1) {
    int flg = 0;
    
    for(int i=0;i<kazu;i++) {
      if(a.size() == 0) {
	if(i == 0) flg++;
	break;
      }
      c.push_back(a[0]);
      a.erase(a.begin());
    }

   
    for(int i=0;i<kazu;i++) {
      if(b.size() == 0) {
	if(i == 0) flg++;
	break;
      }
      c.push_back(b[0]);
      b.erase(b.begin());
    }
 

    if(flg==2) break;
  }


}


int main() {

  int n,r;

  while(cin >> n >> r) {
    a.clear();
    b.clear();
    c.clear();

    for(int i=n/2;i<n;i++) a.push_back(i);
    for(int i=0;i<n/2;i++) b.push_back(i);

    for(int q=0;q<r;q++){
      int kazu;
      cin >> kazu;
      shuffle(kazu);
      a = c;
      for(int i=0;i<n/2;i++) {
	b.push_back(a[0]);
	a.erase(a.begin());
      }
      c.clear();
    }
   
    cout << a[n-1] <<endl; 
  }

  return 0;
}

Measured memory_bytes: 1224
N=int(input())
A=sorted(list(map(int,input().split(' '))))
acc=[A[0]]
ans =1
for i in A[1:]:
    acc.append(acc[-1]+i)
for i in range(N-1,0,-1):
    if A[i]>acc[i-1]*2:
        print(N-i)
        exit()
print(N)

Measured memory_bytes: 14320
#include<cstdio>
int main(void){
	long long n, a;
	scanf("%lld", &n);
	n++;
	a = 0;
	while (n >= 10){
		a += 9;
		n = n / 10;
	}
	a += n;
	a--;
	printf("%lld\n", a);
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		//n角形のnの取得
		int n = scan.nextInt();
        //n角形の内角の和
        int ans = (n-2) * 180;
        	System.out.println(ans);
	}

}


Measured memory_bytes: 20820
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb  push_back
#define eb  emplace_back
#define scan(a,n)  for(int i = 0; i < n;i++)cin >> a[i];
#define print(a,n)  for(int i = 0;i < n;i++)cout <<a[i] <<' ';cout<<endl;
#define w(x)  int x; cin>>x; while(x--)
#define endl  '\n'
#define vi  vector<int>
#define rng(x) x.begin(),x.end()

// Tushar Goyal : Chalie Shuru karte hai

void solve()
{
	int cnt = 0;
	string s, t;
	cin >> s;
	cin >> t;

	for (int i = 0 ; i < s.size() ; i++)
	{
		if (s[i] != t[i])cnt++;
	}

	cout << cnt << endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    w(T)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3796
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c, x, ans = 0;
    cin >> a >> b >> c >> x;
    for(int i = 0; i <= a; ++i) {
        for(int j = 0; j <= b; ++j) {
            int num50 = (x - 500*i - 100*j)/50;
            if(num50 >= 0 && num50 <= c) ans++;
        }
    }
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
int H,W;
  cin >> H >> W;
  // 周り8方向へ移動
   int dh[] = {-1, -1, 0, 1, 1, 1, 0, -1};
   int dw[] = {0, -1, -1, -1, 0, 1, 1, 1};

   string map[60];
   for(int i=0;i<H;i++) cin >> map[i];

   for(int i=0;i<H;i++){
     for(int j=0;j<W;j++){
       if(map[i][j]=='.'){
         int cnt=0;
          for(int k=0;k<8;k++){
            int h=i+dh[k];
            int w=j+dw[k];
              if(h>=0 && h<H && w>=0 && w<W && map[h][w]=='#'){
                cnt++;
              }
              map[i][j]='0'+cnt;//map[i][j]はchar型なので'0'+することでintからcharにする

          }
       }
     }
   }
   for(int i=0;i<H;i++){
     cout << map[i] << endl;
   }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

#define rp(i,n) for(int i=0;i<n;i++)
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define lrp(i,n) for(long long i=0;i<n;i++)
#define lrep(i,m,n) for(long long i=m;i<=n;i++)
#define all(a) a.begin(),a.end()
#define pb push_back

typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int max=0,x=0;
    rp(i,n){
        if(s.at(i)=='I'){
            x++;
        }else if(s.at(i)=='D'){
            x--;
        }
        max = (max<x?x:max);
    }
    cout << max << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define _USE_MATH_DEFINES
#include <math.h>

double calcArea(double x);
double calcAround(double x);

int main()
{
	double radius, area, around;

	std::cin >> radius;

	area = calcArea(radius);
	around = calcAround(radius);

	std::cout << std::fixed << area << ' ' << around << std::endl;

	return 0;
}

double calcArea(double x)
{
	double area = x * x * M_PI;
	return area;
}

double calcAround(double x)
{
	double around = x * 2 * M_PI;
	return around;
}


Measured memory_bytes: 3264
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))
    a = [list(map(int, readline().split())) for _ in range(h)]
    b = [list(map(int, readline().split())) for _ in range(h)]

    diff = [[abs(an - bn) for an, bn in zip(arow, brow)] for arow, brow in zip(a, b)]

    dp = [[1 << (80 * 160 + 1) for _ in range(w)] for _ in range(h)]
    dp[0][0] |= 1 << diff[0][0]

    from itertools import product

    for row, col in product(range(h), range(w)):
        diff_cur = diff[row][col]
        prevset = 0

        if row - 1 >= 0:
            prevset |= dp[row - 1][col]
        if col - 1 >= 0:
            prevset |= dp[row][col - 1]

        dp[row][col] |= (prevset << diff_cur)
        dp[row][col] |= (prevset >> diff_cur)
        temp = 0
        for i in range(diff_cur):
            if prevset >> i & 1:
                temp += (1 << diff_cur - i)
        dp[row][col] |= temp

    for i in range(12801):
        if dp[h - 1][w - 1] >> i & 1:
            print(i)
            sys.exit()


if __name__ == '__main__':
    main()


Measured memory_bytes: 61276
def f(x):
  while p[x]>0: x = p[x]
  return x
N,M = map(int,input().split())
p = [-1]*N
for _ in range(M):
  A,B = map(lambda x:f(int(x)-1),input().split())
  if A==B: continue
  elif A<B: A,B=B,A
  p[A] += p[B]
  p[B] = A
print(sum(i<0 for i in p)-1)

Measured memory_bytes: 11056
// C: Travelling Plan
"use strict";

const DEBUG_MODE = false;
const rawInput = DEBUG_MODE
  ? "2\n1 19"
  : require("fs")
      .readFileSync("/dev/stdin", "utf8")
      .trim();

const process = inputRaw => {
  const mainInputs = inputRaw.split("\n");
  const nodeCount = parseInt(mainInputs[0]);
  const paddedNodes = [
    0,
    ...mainInputs[1].split(" ").map(item => parseInt(item)),
    0,
  ];

  const totalDistance = paddedNodes.reduce(
    (acc, curr, index) =>
      index === 0 ? acc : acc + Math.abs(curr - paddedNodes[index - 1]),
    0
  );

  for (let i = 1; i < nodeCount + 1; i++) {
    const previousNode = paddedNodes[i - 1];
    const skippedNode = paddedNodes[i];
    const nextNode = paddedNodes[i + 1];

    const distanceToSubtract =
      Math.abs(skippedNode - previousNode) + Math.abs(skippedNode - nextNode);
    const distanceToAdd = Math.abs(previousNode - nextNode);

    console.log(totalDistance - distanceToSubtract + distanceToAdd);
  }
};

process(rawInput);


Measured memory_bytes: 44288
#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
#include <bitset>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long ll;

int main() {

	vector<string> str = { "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT" };
	string str2;
	cin >> str2;

	rep(i, 7) {
		if (str2 == str.at(i)) {
			cout << 7 - i << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 256
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

n_p = p[0:x]
n_q = q[0:y]

l = n_p +n_q +r
l.sort(reverse=True)

ans =0
for i in range(x+y):
    ans += l[i]

print(ans)

Measured memory_bytes: 110828
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<long long, long long>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vector<double> p(n);
  rep(i, n) {
    cin >> p[i];
  }

  int target = n/2 + 1;

  double dp[n+1][target+1];

  rep(i, n+1) {
    rep(j, target+1) {
      dp[i][j] = 0;
    }
  }

  dp[0][0] = 1;

  for(int i=0; i<n; i++) {
    for(int j=0; j<target; j++) {
      dp[i+1][j+1] += dp[i][j] * p[i];
      dp[i+1][j] += dp[i][j] * (1 - p[i]);
    }
  }

  double ans = 0;
  for(int j=0; j<target; j++) {
    ans += dp[n][j];
  }
  cout << setprecision(11) << 1 - ans << endl;
}

Measured memory_bytes: 35456
import math 
a,b,x = map(int,input().split())
 
if x >= a**2*b/2:
    tan = 2*(b/a-x/(a**3))
    y = math.atan(tan)
else :
    tan = a*(b**2)/(2*x)
    y = math.atan(tan)

print(math.degrees(y))

Measured memory_bytes: 9224
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n; 
    cin >> n;
    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; ++i)
    	cin >> a[i] >> b[i] >> c[i];
    vector<vector<int>> dp(3, vector<int>(2));
    dp[0][0] = a[0];
    dp[1][0] = b[0];
    dp[2][0] = c[0];
    for (int i = 1; i < n; ++i) {
    	dp[0][1] = a[i] + max(dp[1][0], dp[2][0]);
    	dp[1][1] = b[i] + max(dp[0][0], dp[2][0]);
    	dp[2][1] = c[i] + max(dp[0][0], dp[1][0]);
    	dp[0][0] = dp[0][1];
    	dp[1][0] = dp[1][1];
    	dp[2][0] = dp[2][1];
    }
    cout << max({dp[0][0], dp[1][0], dp[2][0]});
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <sstream>
#include <fstream>

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

using namespace std;

int main() {
  int N;
  cin >> N;
  long long a;

  long long ans = 0;
  for (int i = 0; i < N; ++i) {
    cin >> a;
    while (true) {
      if (a % 2 == 0) {
	a /= 2;
	ans++;
      }
      else {
	break;
      }
    }
  }
  cout << ans << '\n';
  
  return 0;
}


Measured memory_bytes: 256
# |X|<=2*10**5
# 除去回数は最大10**5
# 10**5 < 10**10000 -> STの繰り返しだったとしても10**10000回に到達することはない

X=input()
st=0
cnt=0
for i in range(len(X)):
    if X[i]=='S':
        st+=1
    else:
        if st>0:
            st-=1
            cnt+=1
print(len(X)-cnt*2)

Measured memory_bytes: 3500
# -*- coding: utf-8 -*-
# 整数の入力
inputs = [int(s) for s in input().split()]
N = inputs[0]
Y = inputs[1]

def check_count():
    for i in range(N+1):
      for j in range(N+1-i):
        k = N - (i+j)
        total = k * 10000 + j * 5000 + i * 1000
        if total == Y:
            return " ".join([str(k), str(j), str(i)])
    return "-1 -1 -1"

print(check_count())


Measured memory_bytes: 9096
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, k; cin >> n >> k;
  string s; cin >> s;
  char c = '1';
  int cnt = 0;
  vector<int> a;
  for (int i = 0; i < s.size(); i++){
    if (s.at(i) == c){ cnt++; continue;}
    a.push_back(cnt);
    c = (c=='0' ? '1':'0');
    cnt = 1;
  }
  a.push_back(cnt);
  if (c=='0') a.push_back(0);
  vector<int> b(a.size()+1, 0);
  for (int i = 1; i <= a.size(); i++){
    b.at(i) = b.at(i-1) + a.at(i-1);
  }
  int ans = 0;
  if (2*k + 1 <= a.size()){
    for (int i = 0; i+2*k < a.size(); i += 2){
      ans = max(ans, b.at(i+2*k+1) - b.at(i));
    }
  }else ans = b.at(a.size());
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1272
n=int(input())
inp=list(map(int,input().split()))
hoge=[0 for i in range(n)]
huga=[0 for i in range(n)]
for i in inp:
  huga[i-1]+=1
  hoge[i-1]=(huga[i-1]-1)*huga[i-1]
some=sum(hoge)//2
for i in inp:
  if(huga[i-1]==2):
    print(some-1)
  else:
    print(some-int(huga[i-1]-1))

Measured memory_bytes: 26140
# 2019-11-13 21:06:16(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, k, *v = [int(x) for x in sys.stdin.read().split()]

    ma = 0
    for a in range(min(n, k)+1):
        for b in range(min(n, k)-a+1):
            take = v[:a] + v[-b:] if b != 0 else v[:a]
            take.sort()
            
            if a + b == 0:
                optimum_sum = 0
            else:
                for i in range(min(k-(a+b), a+b)-1, -1, -1):
                    if take[i] > 0:
                        continue
                    else:
                        optimum_sum = sum(take[i+1:])
                        break
                else:
                    optimum_sum = sum(take)
        
            ma = max(ma, optimum_sum)
    
    print(ma)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3188
#include <stdio.h>
#include <math.h>

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n != 0) {
        double s[1024];
        int i;
        double ave = 0, sd = 0;
        
        for (i = 0; i < n; i++) {
            if (scanf("%lf", &s[i]) != 1) {
                return 1;
            }
            ave += s[i];
        }
        
        ave /= n;
        for (i = 0; i < n; i++) {
            sd += (s[i] - ave) * (s[i] - ave);
        }
        printf("%.15f\n", sqrt(sd / n));
    }
    return 0;
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << x << endl

ll a[100010];
ll s[100010];
ll sp[100010];

ll sum(ll l, ll r, ll *acc){
    return acc[r] - acc[l];
}

signed main(){
    int n, k;
    while(cin >> n >> k){
        s[0] = 0;
        sp[0] = 0;
        rep(i, n){
            cin >> a[i];
            s[i+1] = s[i] + a[i];
            sp[i+1] = sp[i] + max<ll>(0, a[i]);
        }

        ll ans = 0;
        rep(i, n-k+1){
            ll other = sum(0, i, sp) + sum(i+k, n, sp);
            ll krange = max<ll>(0, sum(i, i+k, s));
            ans = max(ans, other + krange);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 2560
n = gets.to_i
ab = gets.chomp.split(" ").map{|a| a.to_i}
a = ab[0]
b = ab[1]
pp = gets.chomp.split(" ").map{|a| a.to_i}

array =Array.new(3)
array.map!{Array.new}
pp.each do |p|
  if p <=a
    array[0].push(p)
  elsif
    a+1<= p && p <= b
    array[1].push(p)
  else
    array[2].push(p)
  end
end
abc=[]
array.each do |ary|
  abc.push(ary.size)
end
p abc.min


Measured memory_bytes: 1788
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main()
{
    int x;
    cin >> x;

    cout << ((x) ? 0 : 1) << endl;
    return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

int main() {
  int n, x;
  cin >> n >> x;
  if (x == 1 || x == 2 * n - 1)
    cout << "No" << endl;
  else {
    cout << "Yes" << endl;
    int cnt = 1;
    rep(i, 2 * n - 1) {
      if (cnt == x - 1) cnt += 3;
      int res;
      if (i == n)
        res = x - 1;
      else if (i == n - 1)
        res = x;
      else if (i == n - 2)
        res = x + 1;
      else
        res = cnt++;
      cout << res << endl;
    }
  }
}


Measured memory_bytes: 1536
#include <algorithm>
#include <cassert>
// #include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
// #include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);
*/
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppiipii;
typedef pair<int, ppiipii> pippiipii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> ppiii;
typedef pair<int, ppiii> pippiii;
typedef pair<int, ll> pill;
typedef pair<int, double> pid;
typedef pair<double, double> pdd;
typedef pair<double, pdd> pddd;
typedef pair<string, string> pss;
// note to self, the below two triggers someone
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef long double ld;

int n, c;
int dp[30][30];
int cnt[3][30];

int main() {
    scanf("%d%d", &n, &c);
    for(int i = 0; i < c; i++) {
        for(int j = 0; j < c; j++) {
            scanf("%d", &dp[i][j]);
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            int t;
            scanf("%d", &t);
            cnt[(i+j)%3][t-1]++;
        }
    }
    ll ret = 1e18;
    for(int x = 0; x < c; x++) {
        for(int y = 0; y < c; y++) {
            if(x==y) continue;
            for(int z = 0; z < c; z++) {
                if(z==y || z==x) continue;
                ll curr = 0;
                for(int b = 0; b < 30; b++) {
                    curr += cnt[0][b] * dp[b][x];
                    curr += cnt[1][b] * dp[b][y];
                    curr += cnt[2][b] * dp[b][z];
                }
                ret = min(ret, curr);
            }
        }
    }
    printf("%lld\n", ret);
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;

int N;
int A[20010],B[20010];

int main(){
	cin >> N;
	for(int i=1;i<=N;i++){
		cin >> A[i];
		B[A[i]] = i;
	}
	for(int i=1;i<=N;i++){
		if(i!=N) cout << 30000*i << " ";
		else cout << 30000*i << endl;
	}
	for(int i=1;i<=N;i++){
		if(i!=N) cout << 30000*(N-i) + B[i] <<" ";
		else cout << 30000*(N-i) + B[i] << endl;
	}
}

Measured memory_bytes: 768
// Author : MohamedSameh
#include <bits/stdc++.h>
typedef long long ll ;
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SZ(a) (int)a.size()
void fo (){fflush(stdout);}
using namespace std;
int n , h , mx ;
ll ans ;
int a[100000];
int main ()
{
cin >> n >> h ;
for (int i =0 ; i < n ;i++)
{
  int u ;
  cin >> u >> a[i];
  mx = max (mx , u );
}
sort(a,a+n);
for (int i = n-1 ; i >= 0 ; i--)
{
  if (h <= 0 )break;
  if (a[i] >= mx )
  {
    ans++;
    h-=a[i];
  }
}
if (h > 0 )ans += h / mx + ( h %mx != 0);

cout << ans <<"\n";
  //cerr << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;

int main(){
    int n;
    cin>>n;
    vector<int> d(n);
    REP(i,n){
        cin>>d[i];
    }
    int sum=0;
    REP(i,n-1){
        FOR(j,i+1,n){
            sum+=d[i]*d[j];
        }
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 256
W, H, N = map(int, input().rstrip().split(' '))
sq = [[0 for i in range(W)] for j in range(H)]
for i in range(N):
    x, y, a = map(int, input().rstrip().split(' '))
    if a == 1:
        # < xi
        for j in range(H):
            for k in range(0, x):
                sq[j][k] = 1

    elif a == 2:
        # xi <=
        for j in range(H):
            for k in range(x, W):
                sq[j][k] = 1
    elif a == 3:
        # < yi
        for j in range(y):
            for k in range(W):
                sq[j][k] = 1
    elif a == 4:
        # yi < 
        for j in range(y, H):
            for k in range(W):
                sq[j][k] = 1


result = 0 
for i in range(H):
    for j in range(W):
        if sq[i][j] == 0:
            result += 1


print(result)



Measured memory_bytes: 3064
#include <stdio.h>

int N;
int K;
int h[100004];
int c[100004];

int getCost(int x, int y) {
	int c = x - y;
	return c < 0 ? c * -1 : c;
}

int cost(int i) {
	if (i >= N - 1)
		return 0;
	if (c[i] != -1)
		return c[i];
	int a = getCost(h[i], h[i + 1]) + cost(i + 1);
	int b;
	for (int x = 2; x <= K && i + x < N; x++) {
		b = getCost(h[i], h[i + x]) + cost(i + x);
		a = a < b ? a : b;
	}
	c[i] = a;
	return c[i];
}

int main()
{
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d", &h[i]);
		c[i] = -1;
	}

	printf("%d", cost(0));
}

Measured memory_bytes: 5632
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    int x = (int)m*(int)pow(100,n);
    if(m == 100)
    {
        x = x+pow(100,n);
    }
    cout << x << endl;

}


Measured memory_bytes: 512
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
count=0
for i in range(n):
  count+=b[i]
for i in range(n-1):
  if a[i]+1==a[i+1]:
    count+=c[a[i]-1]
print(count) 

Measured memory_bytes: 3064
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);

    for (auto &x : a) {
        cin >> x;
    }

    int t = n - 1;

    int ans = 0;

    for (int i = 0; i <= t; i += 2) {
        if (a.at(i) % 2 == 1) {
            ans++;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    int N;cin >> N;
    deque<LL> a;
    LL tmp;
    int i = 0;
    if(N%2 == 0){
        while(i != N){
            if(i%2 == 0){
                cin >> tmp;
                a.push_back(tmp);
                i++;
            }
            else{
                cin >> tmp;
                a.push_front(tmp);
                i++;
            }
        }
    }
    else{
        while(i != N){
            if(i%2 == 0){
                cin >> tmp;
                a.push_front(tmp);
                i++;
            }
            else{
                cin >> tmp;
                a.push_back(tmp);
                i++;
            }
        }
    }
    rep(i,N)cout << a[i] << " ";
    cout << endl;
}


Measured memory_bytes: 3840
package main

import (
	"fmt"
	"math"
	"sort"
)

func NextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

func abs(x int) int {
	if x > 0 {
		return x
	} else {
		return -x
	}
}

func main() {
	var n, sumx, sumy int
	var ans, c, tmp float64
	fmt.Scan(&n)

	coords := make([][]int, n)
	for i := range coords {
		coord := make([]int, 2)
		fmt.Scan(&coord[0], &coord[1])
		coords[i] = coord
	}
	order := make([]int, n)
	for i := range order {
		order[i] = i
	}
	for ; ; c++ {
		tmp = 0
		for i := 0; i < n-1; i++ {
			sumx = abs(coords[order[i]][0] - coords[order[i+1]][0])
			sumy = abs(coords[order[i]][1] - coords[order[i+1]][1])
			tmp += math.Sqrt(float64(sumx*sumx + sumy*sumy))
		}
		ans += tmp
		if !NextPermutation(sort.IntSlice(order)) {
			break
		}
	}
	fmt.Println(ans / (c + 1))
}


Measured memory_bytes: 1792
n,m = map(int,input().split())
dp = [0]+[10**8+10]*(2**n-1)
#len(dp)==16　（2**n）　扉の開閉状態
#dp: その開閉状態を実現するための鍵の値段の最小値

#それぞれの鍵について
for i in range(m):
  a,b = map(int,input().split())
  #x: 開く扉の番号
  #2**(1-1)==000000000001   2**(12-1)==100000000000
  #sは　100010111000みたいなやつ（その鍵で開く扉が１）
  s = sum([2**(x-1) for x in list(map(int,input().split()))])
  for j in range(2**n):
    #| : or
    #（ある状態＋その鍵を使って開けられるやつ）の状態　　もともとの数値か、鍵を使うか
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)



Measured memory_bytes: 48088