akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    int x[110];
    int y[110];
    int h[110];
    for(int i = 0; i < N; i++)
    {
        cin >> x[i] >> y[i] >> h[i];
    }

    int c_correct = 0;
    int final_corrent_num[3];
    long long H;
    int clear_pos = -1;
    
    for(int k = 0; k < N; k++)
    {
        if (h[k] > 0) {
            clear_pos = k;
            k = (1 << 30);
        }
    }
    
    if (1 < N) {
        for(int c_x = 0; c_x <= 100; c_x++)
        { 

            for(int c_y = 0; c_y <= 100; c_y++)
            {
                H = h[clear_pos] + abs(x[clear_pos] - c_x) + abs(y[clear_pos] - c_y);
                for (int i = 0; i < N; i++)
                {
                    if (h[i] == max((int)H - abs(x[i] - c_x) - abs(y[i] - c_y), 0))
                    {
                        c_correct++;
                    } else {
                        break;
                    }
                }
                
                if (c_correct == N) {
                    final_corrent_num[0] = c_x;
                    final_corrent_num[1] = c_y;
                    final_corrent_num[2] = H;
                    c_x = (1 << 30);
                    c_y = (1 << 30);
                    H = (1 << 30);
                }
                c_correct = 0;
            }

        }
    } else {
        final_corrent_num[0] = x[0];
        final_corrent_num[1] = y[0];
        final_corrent_num[2] = h[0];
    }
    
    cout << final_corrent_num[0] << " " << final_corrent_num[1] << " " << final_corrent_num[2] << endl;
    
    return 0;
}


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

using ld = long double;
using P = complex<ld>;
const ld PI = acos(-1);
ld r,x,y;
int n;

ld cross(P a, P b){
    return imag(b*conj(a));
}

int main(){
    while(cin >> r >> x >> y >> n){
        P Q(x/r,y/r);
        ld b = PI/2;
        for(int i = 0; i < n; ++i){
            ld t;
            cin >> t;
            t = 2*PI * t/100;
            b -= t;
            ld a = b + t;
            P A = polar<ld>(1.,a);
            P B = polar<ld>(1.,b);
            ld org = t;
            ld mod = org + cross(A,Q) - cross(B,Q);
            cout << floor(mod/org*100) << (i == n-1 ? "\n" : " ");
        }
    }
}

Measured memory_bytes: 3596
import math

N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

count = 0
for i in range(N-1):
  for j in range(i+1, N):
    f = 0
    for k in range(D):
      f += (X[i][k] - X[j][k])**2
    if math.sqrt(f).is_integer():
      count += 1

print(count)

Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(10**9)

N,Q,*abpx=map(int,sys.stdin.read().split())

graph=[[] for _ in range(N)]
for a,b in zip(*[iter(abpx[:2*(N-1)])]*2):
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

f=[0]*N
for p,x in zip(*[iter(abpx[2*(N-1):])]*2):
    p-=1
    f[p]+=x

ans=[0 for _ in range(N)]
visited=[False]*N
def c(i,p):
    if visited[i]:
        return 
    visited[i]=True
    w=f[i]+p
    ans[i]=w
    ch=graph[i]
    for x in ch:
        c(x,w)

c(0,0)
print(*ans)

Measured memory_bytes: 271376
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def main():

    data = list(input())
    num = len(data)

    pre = ''
    kari = ''
    ans1 = 0
    for i in range(num):
        now_str = kari + data[i]
        if now_str == pre:
            kari += data[i]
        else:
            ans1 += 1
            kari = ''
            pre = now_str

    pre = data[0]
    kari = ''
    ans2 = 0
    for i in range(num):
        now_str = kari + data[i]
        if now_str == pre:
            kari += data[i]
        else:
            ans2 += 1
            kari = ''
            pre = now_str

    print(max(ans1, ans2))



if __name__ == '__main__':
    main()



Measured memory_bytes: 61936
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
a = readInts()

a.sort(reverse=True)

if n==1:
	print(math.ceil(a[0]/(k+1)))
	exit()

def get(left, right):
	l = (right-left)//2+left
	ans = 0
	for i in a:
		ans+=math.ceil(i/l)-1
	#print(l, ans, left, right)
	return ans,l

def nibu(left,right):
	ans,l = get(left, right)

	if left<right:
		if ans<=k:
			return nibu(left,l)
		else:
			return nibu(l+1, right)
	else:
		return right


print(nibu(1,a[0]))


Measured memory_bytes: 106240
#include <bits/stdc++.h>
#define rep(i, n) for (long long i = 0; i < (n); ++i)

using namespace std;

typedef pair<int, int> p;
typedef long long ll;
const int inf = 1000000007;

int main() {
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) {
    cin >> a[i];
    a[i]--;
  }
  ll sid = 0;
  vector<ll> sumi(n, -1);
  vector<ll> s;
  ll beg = 0;
  ll t = 0;
  sumi[0] = 0;
  s.push_back(0);
  // cout << beg << ", ";
  for (ll i = 1; i < n; i++) {
    beg = a[beg];
    // cout << beg << ", ";
    if (sumi[beg] == -1) {
      sumi[beg] = i;
      s.push_back(beg);
    } else {
      t = i - sumi[beg];
      sid = sumi[beg];
      break;
    }
  }
  // cout << endl;
  // cout << sid << ", " << t << endl;
  ll ans = 0;
  if (k <= sid) {
    // rep(i, k) { ans = a[ans]; }
    cout << s[k] + 1 << endl;
    return 0;
  }
  ll id = (k - sid) % t;
  // rep(i, sid + id) { ans = a[ans]; }
  cout << s[sid + id] + 1 << endl;
  return 0;
}

Measured memory_bytes: 8476
#include <bits/stdc++.h>
using namespace std;
//using Graph = vector<vector<edge>>;
using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define query int qq;std::cin >> qq;rep(qqq,qq)
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
//#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvector(name,typ,m,n)vector<vector<typ> > name(m,vector<typ> (n))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout <<"Case #" <<qqq+1<<": "
#define res resize
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout << a<<" "<<b <<" "<< c<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define ssum(a) accumulate(a,0ll) 

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
//typedef long long T;
ll ceil(ll a,ll b){
    return ((a+b-1)/b);
}
const int INF = 1000000000;
const ll INF64 = 9223372036854775807ll;
const ll MOD = 1000000007ll;
const dou pi=3.141592653589793;
//mapは、if関数などで覗いただけで構成されるので注意しよう！
//std::vector<vector<int>> g;


//std::vector<std::set<int>> g;

int ketawa(ll n){  //各桁の和を計算する
    ll dum=0ll;
    while(n!=0){
        dum+=n-(n/10)*10;
        n/=10;
    }
    return dum;
}

int main(){
    int n;
    std::cin >> n;
    if(n%ketawa(n)==0)std::cout << Yes << std::endl;
    else std::cout << No << std::endl;
}




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

using namespace std;
using ll=long long;
const int N = 2e5+10; 
int a[N];
ll dp[3][N];
void solve() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int hole = 1 + (n&1);
    memset(dp, 0xc0, sizeof dp);
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= hole; j++) {
            for (int k = 0; k+j <= hole; k++) {
                int ii = i + (i>0) + k;
                dp[k+j][ii+1] = max(dp[k+j][ii+1], dp[j][i] + a[ii]);
            }
        }
    }
    ll res = max(dp[hole][n], dp[hole-1][n-1]);
    if (hole == 2) res = max(res, dp[hole-2][n-2]);
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 9084
#include <stdio.h>

int main(){
  int big,small,i,j;
  scanf("%d%d",&big,&small);
  if(small>big){
    i=big;
    big=small;
    small=i;
  }
  j=big%small;
  while(j!=0){
    big=small;
    small=j;
    j=big%small;
	 }
    printf("%d\n",small);
    
  return 0;
}




Measured memory_bytes: 2140
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;

int main(){
  string s;cin>>s;
  int n=(int)s.size();
  if(n==26){
    if(s=="zyxwvutsrqponmlkjihgfedcba"){cout<<-1<<endl;return 0;}
    else{
      for(int i=n-1;i>=0;i--){
        if(s[i-1]<s[i]){
          char c='z';
          for(int j=i;j<n;j++){
            if(s[j]>s[i-1])c=min(c, s[j]);
          }
          cout<<s.substr(0, i-1)<<c<<endl;
          return 0;
        }
      }
    }
  }else{
    map<int, bool> exist;
    for(int i=0;i<n;i++){
      exist[int(s[i]-'a')]=true;
    }
    for(int i=0;i<26;i++){
      if(!exist[i]){cout<<s<<char('a'+i)<<endl;return 0;}
    }
  }
}


Measured memory_bytes: 256
#pragma region RegionDefs
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,l,r) for(int i=(l),i##_len=(r);i<i##_len;++i)
#define all(x) begin(x),end(x)
using namespace std;
const int INF = 1e9;
template<class T=int> using V = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)
//時間が厳しいとき使う
#define INI(...) int __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
template<class T>bool chmax(T &a, const T &b) {if (a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a>b) {a=b; return 1;} return 0;}
#define y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#define YN(e) cout << ((e) ? "YES" : "NO") << endl
#define yn(e) cout << ((e) ? "Yes" : "No") << endl
#pragma endregion RegionDefs

void solve()
{
    IN(x);
    ll d = 100;
    ll i = 0;
    while (true)
    {
        d += d / 100;
        ++i;
        if (d >= x)
        {
            cout << i << endl;
            return;
        }
    }
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 3648
open Batteries
module EnumL = Enum.Labels
module ListL = List.Labels
module ArrayL = Array.Labels

let dbg0 x = Printf.eprintf "[debug]%s\n" @@ dump x
let dbg1 x = dbg0 x; x

let id = identity

let (++) n m = List.range n `To m
let (++-) n m = if n >= m then List.range n `Downto m else []
let (++^) n m = if n < m then List.range n `To (pred m) else []

module ModOp = struct
  let prime = 1_000_000_007
  let (-) a b = (a + prime - b) mod prime
  let (+) a b = (a + b) mod prime
  let ( * ) a b = (a * b) mod prime

  let rec pow x n =
    if n = 0 then 1
    else if n mod 2 = 0 then pow (x*x) (n/2)
    else x * pow (x*x) (n/2)
end

let scan fmt = Scanf.sscanf (read_line ()) fmt

let scan_lines n fmt f =
  if n = 0 then []
  else List.map (fun _ -> scan fmt f) (1 ++ n)

let scan_list ?sep cnv =
  let line = read_line () in
  (match sep with
   | None -> List.map String.of_char @@ String.to_list line
   | Some sep -> String.split_on_char sep line)
  |> List.map cnv

let scan_array ?sep cnv = Array.of_list @@ scan_list ?sep cnv

let scan_matrix n m e ?sep conv =
  let arr = Array.make_matrix n m e in
  ListL.iter (0 ++^ n)
    ~f:(fun i -> arr.(i) <- Array.of_list @@ scan_list ?sep conv);
  arr

let atoi c = Char.code c - Char.code '0'

let rec powerset = function
  | [] -> [[]]
  | hd::tl ->
    let pws =  powerset tl in
    pws @ ListL.map pws ~f:(fun pw -> hd::pw)

let permutations l =
  let rec interleave x = function
    | [] -> [[x]]
    | (hd::tl) as l ->
      (x::l) :: (interleave x tl |> ListL.map ~f:(fun l -> hd::l)) in
  let rec aux = function
    | [] -> [[]]
    | a::rest ->
      aux rest |> ListL.map ~f:(interleave a) |> List.concat in
  aux l

let intersection l =
  EnumL.filter ~f:(fun x -> EnumL.exists ~f:((=) x) @@ Enum.clone l)

let zip l m =
  let n = min (List.length l) (List.length m) in
  List.combine (List.take n l) (List.take n m)

let lower_bound n f =
  let rec aux l u =
    if u - l > 1 then
      let m = (l + u) / 2 in
      if f m then aux l m
      else aux m u
    else u in aux (-1) n

let between n x m = n <= x && x < m

let x = scan "%d" id

let () =
  ListL.fold_left [500;5] ~init:(0,x) ~f:(fun (n,x) i ->
      (n+((x/i) * if i = 500 then 1000 else 5), x mod i))
  |> Tuple2.first
  |> Printf.printf "%d\n"


Measured memory_bytes: 5372
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  lint n; cin >> n;
  vector<lint> a(n + 1);
  for (int i = 0; i <= n; i++) {
    cin >> a[i];
  }

  if (n == 0) {
    if (a[0] == 1) {
      cout << 1 << endl;
    } else {
      cout << -1 << endl;
    }
    return 0;
  }

  if (a[0] != 0) {
    cout << -1 << endl;
    return 0;
  }


  vector<lint> b(n + 1);
  b[0] = 1;
  for (int i = 1; i <= n; i++) {
    b[i] = b[i - 1] * 2 - a[i];
    b[i] = min(b[i], INF);
    if (b[i] < 0) {
      cout << -1 << endl;
      return 0;
    }
  }

  vector<lint> c(n + 1);
  lint ans = a[n];
  c[n] = a[n];
  for (int i = n - 1; i >= 0; i--) {
    c[i] = min(c[i + 1] + a[i], b[i] + a[i]);
    ans += c[i];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 5640
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
int main() {
	int N, L; cin >> N >> L;
	multiset<string> S;
	for (int i = 0; i < N; i++) {
		string A; cin >> A;
		S.insert(A);
	}
	for (auto itr = S.begin(); itr != S.end(); itr++)
		cout << *itr;
	cout << endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
int min(int x, int y) {
	return x < y ? x : y;
}
int nm(int x) {
	int numb = 0;
	for (;;) {
		if (x == 0) {
			return numb;
		}
		x = x / 10;
		++numb;
	}
}
int main() {
	int n, ans=0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		if (nm(i) % 2 == 1) {
			ans++;
		}
	}
	printf("%d", ans);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    string S;
    cin >> S;
    int K = S.size();
    int i = 0;
    while(i < S.size()){
        if(S[i] == S[i+1]){
            i += 2;
            K--;
        }
        ++i;
    }
    cout << K;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    map<int, int> mp;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        mp[A[i]] = i;
    }
    vector<int> B = A;
    sort(B.begin(), B.end());

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (abs(i - mp[B[i]]) % 2 == 1) {
            cnt++;
        }
    }
    cout << cnt / 2 << endl;
}


Measured memory_bytes: 5760
N = int(input())
src = [input() for i in range(N)]

def isok(b):
    for i in range(N-1):
        for j in range(i+1, N):
            i2 = (i+b)%N
            j2 = (j+b)%N
            if src[i][j2] != src[j][i2]:
                return False
    return True

ans = 0
for i in range(-N+1,N):
    if isok(i):
        ans += N-abs(i)
print(ans)


Measured memory_bytes: 41452
#coding=utf-8

def solve(n, ss):
    return len(set(ss))

def main():
    n = int(input())
    ss = input().split(' ')
    ans = solve(n, ss)
    if ans == 3:
        print("Three")
    elif ans == 4:
        print("Four")

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
int main()
{
	string s;
	cin>>s;
	string t="";
	ll ans=0;
	ll cnt=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='A')
			t+='A';
		else if(s[i]=='B')
		{
			if(i+1<s.length()&&s[i+1]=='C')
			{
				t+='B';
				i++;
			}
			else t+=' ';
		}
		else{
			t+=' ';
		}
	}
	for(int i=0;i<t.length();i++)
	{
		if(t[i]=='A') cnt++;
		else if(t[i]=='B') ans+=cnt;
		else cnt=0;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 900
use std::io;

// read a line(without line feed)
fn read_line() -> String {
    let mut in_str = String::new();
    io::stdin().read_line(&mut in_str).unwrap();
    return in_str.trim().to_string();
}

fn read_words_in_line() -> Vec<String> {
    let s = read_line();
    return s.split_whitespace().map(|x| x.to_string()).collect::<Vec<String>>()
}

fn read_t_in_line<T : std::str::FromStr>() -> Vec<T> {
    let mut v : Vec<T> = Vec::new();
    for e in read_words_in_line().iter().map(|x| x.parse::<T>()) {
        if let Ok(r) = e {
            v.push(r);
        }
        else{
            return Vec::new();
        }
    }
    return v;
}

// fn div_ceil<T : std::ops::Add<Output = T> + std::ops::Sub<Output = T> + std::ops::Add<Output = T>>(x : T, y : T) -> T {
//     return (x + y - 1) / y;
// }

fn main(){
    let s = read_line();
    let s_bytes = s.as_bytes();
    let cc = s_bytes[s.len() / 2];

    // let cc = s.chars().nth(s.len() / 2).unwrap();

    for i in 0..(s.len() / 2) {
        let j1 = s.len() / 2 - 1 - i;
        let j2 = s.len() - 1 - j1;
        let c1 = s_bytes[j1];
        let c2 = s_bytes[j2];
        if !(c1 == c2 && c1 == cc) {
            println!("{}", s.len() - j1 - 1);
            return;
        }
    }
    println!("{}", s.len());
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#include<queue>
#define REP(i,a,b) for(int (i)=0; (i)<(a); (i)++)
using namespace std;


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N,H,W,ans=0;
  cin>>N>>H>>W;
  int A[N],B[N];
  for(int i=0;i<N;i++){
    cin>>A[i]>>B[i];
    if(A[i]>=H && B[i]>=W){
      ans++;
    }
  }
  cout<<ans;

  return 0;
}


Measured memory_bytes: 256
#include <cassert>
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[1<<n]; for (int i = 0; i < 1<<n; i++) cin >> a[i];
    int b[1<<n], c[1<<n] = {-1};
    b[0] = 0;
    for (int s = 1; s < 1<<n; s++) {
        int p = s, q = -1;
        for (int i = 0; i < n; i++) {
            if (s&(1<<i)) {
                int t = s^(1<<i);
                if (c[t] >= 0 && a[p] < a[c[t]]) { p = b[t]; q = c[t]; }
                else if (a[p] < a[b[t]]) { q = p; p = b[t]; assert(p != q);}
                else if (q == -1 || a[q] < a[b[t]] && p != b[t]) q = b[t];
                else if (q == -1 || a[q] < a[c[t]] && p != c[t]) q = c[t];
            }
        }
        b[s] = p; c[s] = q;
    }
    int acc = -1;
    for (int s = 1; s < 1<<n; s++) {
        assert(b[s] != c[s]);
        acc = max(acc, a[b[s]] + a[c[s]]);
        cout << acc << endl;
    }
}



Measured memory_bytes: 6144
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
int i,j,l,n,m,k[19],s[19][19],p[19],c,f,ans;
int main()
{
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>k[i];
		for(j=1;j<=k[i];j++)
		{
			cin>>s[i][j];
		}
	}
	for(i=1;i<=m;i++)cin>>p[i];
	for(j=0;j<(1<<n);j++)
	{
		c=0;
		for(i=1;i<=m;i++)
		{
			f=0;
			for(l=1;l<=k[i];l++)
			{
				if(j&(1<<(s[i][l]-1)))f^=1;
			}
			if(f==p[i])c++;
		}
		if(c==m)ans++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0593

"""
import sys
from sys import stdin
from collections import namedtuple, Counter
input = stdin.readline


class RMQ(object):
    INT_MAX = 2**31 - 1

    def __init__(self, nn, init_val=0):
        self.n = 1
        while self.n < nn:
            self.n *= 2
        self.dat = [init_val] * ((2 * self.n)-1)

    def update(self, k, a):
        # A[k]???a?????´??°?????????????????°???????????¨?????´??°
        k += (self.n - 1)
        self.dat[k] = a

        while k > 0:
            k = (k - 1) // 2        #  ??????index??????
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2]) #  ???????????¨??????????????????????°?????????????????????´??°

    def query(self, a, b, k, l, r):
        # [a, b)???????°????????±??????? (0????????§b???????????????)
        # ??????????????¨?????????query(a, b, 0, 0, n)?????¢??§??????????????????k, l, r???????????????????????´??°?????????
        if r <= a or b <= l:        #  ?????????????????§??¨??????????????????
            return RMQ.INT_MAX
        if a <=l and r <= b:
            return self.dat[k]           #  ???????????°???????????????????????§????????°????????¨??????????????????????°?????????????????????????
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2) #  ????????°????????????????°????
            vr = self.query(a, b, k*2+2, (l+r)//2, r) #  ????????°????????????????°????
            return min(vl, vr)

    def find(self, s, t):
        return self.query(s, t+1, 0, 0, self.n)



event = namedtuple('event', ['num', 'cost'])
def main(args):
    N, M = map(int, input().split())
    rq = RMQ(1001, 999999)
    events = [event(i+1, int(input())) for i in range(N)]
    events.reverse()
    for e in events:
        rq.update(e.cost, e.num)

    # ????\¨
    votes = []
    for _ in range(M):
        v = int(input())
        result = rq.find(0, v)
        votes.append(result)
    ans = Counter(votes).most_common(1)[0][0]
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

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

using namespace std;

int main(){
   int n,ans=0;
   string s;
   cin >> n >> s;
   for(int i=0;i<n-2;++i){
       if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
            ++ans;
   }
   cout<<ans<<'\n';
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
typedef long long ll;
using namespace std;

int main() {
	int N;
	ll T,sum=0;
	cin >> N >> T;
	if (N == 1) {
		cout << T << endl;
		return 0;
	}
	vector<ll>t(N);
	for (int i = 0; i < N; ++i)cin >> t[i];
	for (int i = 0; i < N - 1; ++i) {
		if (t[i] + T <= t[i + 1])sum += T;
		else sum += (t[i + 1] - t[i]);
	}
	sum += T;
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdio.h>
int compare(const void *a,const void *b){
    if(*(int *)a>*(int *)b)return -1;
    return 1;
}
int main(int argc, const char * argv[]) {
    int n,k;
    scanf("%d%d",&k,&n);
    int a[n],d[n];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(i==0)continue;
        d[i-1]=a[i]-a[i-1];
    }
    d[n-1]=k-a[n-1]+a[0];
    qsort(d,n,sizeof(int),compare);
    printf("%d",k-d[0]);
    return 0;
}


Measured memory_bytes: 2556
S = input().strip()
cond1 = S[0] == 'A'
cond2 = S[2:-1].count('C') == 1
cond3 = S.replace('A', '').replace('C', '').islower()
if all([cond1, cond2, cond3]):
  print('AC')
else:
  print('WA')

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using namespace std;
typedef long long ll;

namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;
using Real = mp::number<mp::cpp_dec_float<1024>>;

#define INCANT cin.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define out(a) cout << a << endl
#define PRINT(V) for (auto v : (V)) cout << v << " "

const int MOD = 1000000007;
const double PI = acos(-1.0);

void solve() {
    ll N;
    cin >> N;
    N = N-1;
    int max_digit=0;
    ll max_v=1;
    while(true){
        max_v = max_v*26;
        max_digit += 1;
        if(N < max_v) break;
        N = N-max_v;
    }
    vector<char> ans(max_digit, 'a');
    rep(i, max_digit){
        int a = N%26;
        N = N/26;
        ans.at(i) = (char)(a+(int)'a');
    }
    reverse(all(ans));
    for(auto i : ans) cout << i;
    cout << endl;
}
int main() {
    INCANT;
    solve();
    return 0;
}




Measured memory_bytes: 3572
#include<stdio.h>
int n,m;
int c[20],array[50001];
void bubblesort(void);
void survey(int,int *);

int main(void){
    int i,v;
    scanf("%d%d",&n,&m);
    for(i = 0;i < m;i++){
        scanf("%d",&c[i]);
    }
    array[0] = 0;
    bubblesort();
    v = 0;
    for(i = 1;i < n + 1;i++){
        survey(i,&v);
    }
    printf("%d\n",array[n]);
    return 0;
}

void bubblesort(void){
    int i,j,k;
    for(i = m;i > 1;i--){
        for(j = 1;j < i;j++){
            if(c[j - 1] > c[j]){
                k = c[j]; c[j] = c[j - 1]; c[j - 1] = k;
            }
        }
    }
    return;
}

void survey(int p, int *q){
    int i,reply;
    if(p >= c[*q + 1] && *q < m - 1){
        (*q)++;
    }
    reply = 50002;
    for(i = 0;i < *q + 1;i++){
        if(reply > array[p - c[i]] + 1){
            reply = array[p - c[i]] + 1;
        }
    }
    array[p] = reply;
}

Measured memory_bytes: 788
#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false);

  string s;
  cin >> s;

  int n = s.size();

  ll ans = 0;
  int lc = 0, buf = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (lc) {
      if (s[i] == 'B') buf++;
      else buf = 0;
    } else {
      if (s[i] == 'A') ans += buf;
      if (s[i] == 'B') buf = 0;
    }
    lc = s[i] == 'C';
  }

  cout << ans << endl;
}


Measured memory_bytes: 720
import itertools

n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))
if p == q:
  print(0)
  exit()
nums = [i for i in range(1,n+1)]
a = [0,0]
now = 0
for k,i in enumerate(itertools.permutations(nums)):
  if i == p or i == q:
    a[now] = k
    now += 1
print(abs(a[1]-a[0]))

Measured memory_bytes: 3064
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include<map>
#include<tuple>
using namespace std;
#define INF 11000000000
#define MAX 110000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;
typedef pair<pair<int,int>,int> p;
typedef pair< pair<int,int>, int> p; 
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)

int par[210000]; //親
int ran[210000]; //木の深さ
int a[210000],b[210000];

// n要素を初期化
void init(int n){
  for(int i=0;i<n;i++){
    par[i]=i;
    ran[i]=0;
  }
}

//木の根を求める
int find(int x){
  if(par[x]==x){
    return x;
  }else{
    return par[x]=find(par[x]);
  }
}

//xとyの属する集合を併合
void unite(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y) return;

  if(ran[x]<ran[y]){
    par[x]=y;
  }else{
    par[y]=x;
    if(ran[x]==ran[y]) ran[x]++;
  }
}

//xとyが同じ集合に属するか否か
bool same(int x,int y){
  return find(x)==find(y);
}


int main(){
    int N,K,L;
    cin>>N>>K>>L;
    init(N);
    for(int i=0;i<K;i++){
        int p,q;
        cin>>p>>q;
        p--; q--;
        unite(p,q);
    }
    for(int i=0;i<N;i++){
        a[i]=find(i);
    }
    init(N);
    for(int i=0;i<L;i++){
        int r,s;
        cin>>r>>s;
        r--; s--;
        unite(r,s);
    }
    for(int i=0;i<N;i++){
        b[i]=find(i);
    }
    map<P,int> M;
    for(int i=0;i<N;i++){
        M[P(a[i],b[i])]++;
    }
    for(int i=0;i<N;i++){
        if(i) cout<<" ";
        cout<<M[P(a[i],b[i])];
    }
    cout<<endl;
}



Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 2e5+5, MOD = 998244353;
ll n, m, k;
ll fact[N], invfact[N];

ll fastexp(ll a, ll x, ll m) {
    if(x == 0) return 1;
    ll ans = 1;
    while(x > 0) {
        if(x&1) ans = (ans*a)%m;
        a = (a*a) % m;
        x /= 2;
    }
    return ans;
}

ll choose(ll n, ll k) {
    if(k < 0 && k > n) return 0;
    return (((fact[n] * invfact[k]) % MOD) * invfact[n-k]) % MOD;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;

    fact[0] = 1; invfact[0] = 1;
    for(int i = 1; i < n; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
        invfact[i] = (invfact[i-1] * fastexp(i, MOD-2, MOD)) % MOD;
    }

    ll ans = (m * fastexp(m-1, n-1, MOD)) % MOD;
    for(int i = 1; i <= k; i++) {
        ll cur = choose(n-1, i);
        cur *= (m * fastexp(m-1, n-i-1, MOD)) % MOD; cur %= MOD;
        ans += cur; ans %= MOD;
    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 6728
import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner kbd = new Scanner(System.in);

    void run(){
	int days = kbd.nextInt();
	int jap = kbd.nextInt();
	int math = kbd.nextInt();
	int maxJ = kbd.nextInt();
	int maxM = kbd.nextInt();

	while(jap>0 || math>0){
	    jap -= maxJ;
	    math -= maxM;
	    days--;
	}
	System.out.println(days);
    }
}

Measured memory_bytes: 17220
mod = 10**9 + 7
s = 'ACGT'
bad = ['AGC', 'ACG', 'GAC', 'ACGC', 'AGGC', 'ATGC', 'AGAC', 'AGGC', 'AGTC']

def valid(a):
    if a[0:3] in bad:
        return False
    if a[1:] in bad:
        return False
    if a in bad:
        return False
    return True

n = int(input())

dp = [[[1 for k in range(4)] for j in range(4)] for i in range(4)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            t = s[k]+s[j]+s[i]
            if t in ['AGC', 'ACG', 'GAC']:
                dp[i][j][k] = 0

for pos in range(3,n):
    nx = [[[0 for k in range(4)] for j in range(4)] for i in range(4)]

    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    t = s[k]+s[j]+s[i]+s[l]

                    if valid(t):
                        nx[l][i][j] += dp[i][j][k]
                        nx[l][i][j] %= mod
    dp = nx

ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[i][j][k]
            ans %= mod
print(ans)


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

signed main(){

    long long n;
    cin >> n;
    vector<long long> a(n);
    for (long long i = 0; i < n; ++i) {
        cin >> a[i];
    }
    const long long inf = 1e18;
    vector<vector<long long> >dp(n+3, vector<long long> (n+3, inf));
    vector<vector<long long> >sz(n+3, vector<long long> (n+3, 0));


    for(long long i = 0; i < n; i++) {
        for (long long j = i; j < n; j++) {
            sz[i][j] = (j == 0 ? 0 : sz[i][j - 1]) + a[j];
//            cost[i][j] = min(cost[i][j], (j == i ? 0 : sz[i][j] + cost[i][j - 1]));
        }
    }


    for(long long i = n-1; i >= 0; i--) {
        for (long long j = i; j < n; j++) {
            for(long long k = 0; k < n-1; k++){
                if(i == j)
                    dp[i][j] = 0;
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sz[i][j]);
            }
        }
    }


    cout << dp[0][n-1] << "\n";

    return 0;
}

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

int main() {
  int M, N;
  while(cin >> M >> N && M) {
    vector<int> books(N);
    for(int i=0; i<N; i++) {
      cin >> books[i];
    }
    
    int l = 1, r = 1500001;
    while(r - l > 1) {
      int m = (l+r)/2;
      int BPS = 0;
      for(int i=0; i<M; i++) {
	int size = m;
	for(;;) {
	  if(BPS == N) break;
	  if(size - books[BPS] < 0) break;
	  size -= books[BPS++];
	}
	if(BPS == N) break;
      }
      if(BPS == N) {
	r = m;
      } else l = m;
    }
    
    cout << l+1 << endl;
  }
  
  return 0;
}

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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
    lint a, b, x;
    cin >> a >> b >> x;
    lint ans = b / x + 1;
    if (a == 0) {
        ans -= 0;
    } else if (a == 1) {
        ans--;
    } else {
        ans -= (a - 1) / x + 1;
    }

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

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100000

typedef struct{
  int key;
  int parent;
  int degree;
  int depth;
  int height;
  int left;
  int right;
}Data;

int Height(Data T[],int id){
  int l_node, r_node;
  l_node = T[id].left;
  r_node = T[id].right;
  if(T[id].left == -1&&T[id].right == -1){
    return 0;
  }
  else{
    if( r_node == -1){
      T[l_node].height = Height(T,l_node);
      return T[l_node].height + 1;
    }
    if(l_node == -1){
      T[r_node].height = Height(T,r_node);
      return  T[r_node].height + 1;
    }
    
    T[l_node].height = Height(T,l_node);
    T[r_node].height = Height(T,r_node);
    
    if(T[l_node].height<=T[r_node].height){
      return T[r_node].height + 1;
    }
    else return T[l_node].height + 1;
  }
}

int main(){
  int i,j,id,n,child,x,count=0,key,l;  Data T[MAX];
  
  scanf("%d",&n);

  for(i=0;i<n;i++){ //?????????
    T[i].parent = T[i].left = T[i].right = T[i].height = -1;
    T[i].depth = 0;
  }
  
  for(i=0;i<n;i++){ //parent,degree
    scanf("%d",&id);
    for(j=0; j<2; j++){
      scanf("%d",&child);
      if(j==0){
	T[id].left = child;
      }
      else {
	T[id].right = child;
      }
      T[child].parent = id;
    }
    if(T[id].left == -1&&T[id].right == -1){
      T[id].degree = 0;
    }
    else if(T[id].left == -1||T[id].right == -1)T[id].degree = 1;
    else T[id].degree = 2;
  }

  //fprintf(stderr,"wa-i\n");
  
  for(id=0;id<n;id++){ //height
    T[id].height = Height(T,id);
  }

  //fprintf(stderr,"wa-i2\n");
  
  for(id=0;id<n;id++){ //depth
    x = id;
    count = 0;
    while(T[x].parent != -1){
      x = T[x].parent;
      count++;
    }
    T[id].depth = count;
  }

  //fprintf(stderr,"wa-i3\n");
  
  for(id=0;id<n;id++){
    printf("node %d: parent = %d, ",id,T[id].parent);

    if(T[id].parent == -1){
      printf("sibling = -1, ");
    }
    else if(id==T[T[id].parent].left){
      printf("sibling = %d, ",T[T[id].parent].right);
    }
    else {
      printf("sibling = %d, ",T[T[id].parent].left);
    }
    printf("degree = %d, depth = %d, height = %d, ",T[id].degree, T[id].depth,T[id].height);
    
    if(T[id].depth == 0)  printf("root\n");
    else if(T[id].left == -1&&T[id].right == -1)printf("leaf\n");
    else printf("internal node\n");
  }
  
  return 0;
}

Measured memory_bytes: 620
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010],b[100010],num[100010],ans,dp[100010];
vector<int> v[100010];
queue<int> q;
int main(){
	cin>>n>>m;
	for (int i=0;i<m;i++){
		cin>>a[i]>>b[i];
		num[b[i]]++;
		v[a[i]].push_back(b[i]);
	}
	for (int i=1;i<=n;i++) if (num[i]==0) q.push(i);
	while(!q.empty()){
		int x=q.front();q.pop();
		for (int i=0;i<v[x].size();i++){
			dp[v[x][i]]=max(dp[x]+1,dp[v[x][i]]);
			num[v[x][i]]--;
			if (num[v[x][i]]==0) q.push(v[x][i]);
		}
	}
	for (int i=1;i<=n;i++) ans=max(ans,dp[i]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 7296
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
#define rep(i,a,n)	for(int i=a;i<n;i++)
#define rrep(i,a,n) for(int i=(a-1);i>=n;i--)
 
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
ll lcm(ll a,ll b){
	ll g=gcd(a,b);
	return a/g*b;
}
 
ll digitsum(ll a){
	ll x=0;
	while(a>0){
		x+=a%10;
		a/=10;
	}
	return x;
}
int main(){
	string s;
	cin>>s;
	bool ans=false;
	rep(i,0,s.size()){
		if(s[i]=='9')ans=true;
	}
	if(ans)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
}

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

#define fi first
#define se second

const int N = 1010;

using namespace std;

int n;
int col[N];
int a[N][N];
vector < int > v[N];

void dfs(int x, int g = 1)
{
        if(col[x]){
                if(col[x] != g){
                        cout << -1 << "\n";
                        exit(0);
                }
                return;
        }
        col[x] = g;
        for(int i = 1; i <= n; i++){
                if(a[x][i]){
                        dfs(i, 3 - g);
                }
        }
}

int solve(int x)
{
        vector < int > g(1, x);
        vector < int > shit(n + 1, 0);
        shit[x] = true;
        int res = 0;

        while(!g.empty()){
                res += 1;
                vector < int > ng;
                for(int x: g){
                        for(int y: v[x]){
                                if(shit[y]){
                                        continue;
                                }
                                ng.push_back(y);
                                shit[y] = true;
                        }
                }
                g = ng;
        }

        return res;
}

int main()
{
        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
        ios_base::sync_with_stdio(0);

        cin >> n;
        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                        char c;
                        cin >> c;
                        a[i][j] = c - '0';
                        if(a[i][j]){
                                v[i].push_back(j);
                        }
                }
        }

        dfs(1);

        int res = 0;
        for(int i = 1; i <= n; i++){
                res = max(res, solve(i));
        }

        cout << res << "\n";
}


Measured memory_bytes: 1280
#include<stdio.h>
int main()
{
	int a,b,c;
	char n[5];
	scanf("%s",&n);
	if(n[0]=='M')
	{
		printf("6");
	}
	if(n[0]=='T')
	{
		if(n[1]=='U')
			printf("5");
		else
			printf("3");
	}
	if(n[0]=='W')
	{
		printf("4");
	}
	if(n[0]=='F')
	{
		printf("2");
	}
	if(n[0]=='S')
	{
		if(n[1]=='U')
			printf("7");
		else
			printf("1");
	}
	return 0;
}



Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll          long long int
#define ios        	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;


int main() 
{   
  ios
  ll n , W ;
  cin>> n>> W ;
  ll wt[n] ;
  ll v[n] ;
  for(int i=0;i<n;i++)
  {
    cin>> wt[i] >> v[i] ;
  }
  ll i, w; 
  ll K[n+1][W+1];  
  for (i = 0; i <= n; i++) 
   { 
       for (w = 0; w <= W; w++) 
       { 
           if (i==0 || w==0) 
               K[i][w] = 0; 
           else if (wt[i-1] <= w) 
                 K[i][w] = max(v[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
           else
                 K[i][w] = K[i-1][w]; 
       } 
   } 
  cout<< K[n][W] ;
  return 0 ;
}


Measured memory_bytes: 79232
#include<bits/stdc++.h>
#define ll long long
#define maxn 200005
ll n,a[maxn],f[maxn];
ll ans;
ll read(){
	ll x=0,c;while(!isdigit(c=getchar()));
	while(x=x*10+c-'0',isdigit(c=getchar()));
	return x;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	if(a[1])return puts("-1"),0;
	for(int i=1;i<n;i++)if(a[i+1]-a[i]>1){return puts("-1"),0;}
	for(int i=2;i<=n;i++)if(a[i]-a[i-1]==1) f[i]=f[i-1]+1,f[i-1]=0; else f[i]=a[i];
	for(int i=1;i<=n;i++)ans+=f[i];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3328
import java.io.*;
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner();
    out = new PrintWriter(new BufferedOutputStream(System.out));

    int N = sc.nextInt();
    int K = sc.nextInt();
    ArrayList<Long> H = new ArrayList<>();
    H.ensureCapacity(N);

    for (int i = 0; i < N; i++) {
      H.add(sc.nextLong());
    }

    Collections.sort(H, Collections.reverseOrder());

    long ans = 0;
    for (long i : H) {
      if (K > 0) {
        K--;
      } else {
        ans += i;
      }
    }

    out.println(ans);

    out.close();
  }

  public static PrintWriter out;

  public static class Scanner {
    BufferedReader br;
    StringTokenizer st;

    public Scanner() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }
    
    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

  }
}

Measured memory_bytes: 61268
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

int F[2100010];

int Mul(int a, int b) {
	return ((a % mod) * (b % mod)) % mod;
}

void fact(void) {
	F[0] = 1;
	F[1] = 1;
	for (int i = 2; i <= 2100000; i++) {
		F[i] = Mul(i, F[i - 1]);
	}
}
int square(int x) {
	return (x * x) % mod;
}

int power(int x, int y) {
	if (y == 0) return 1;
	else if (y == 1) return x % mod;
	else if (y % 2 == 0) return square(power(x, y / 2)) % mod;
	else return square(power(x, y / 2)) * x % mod;
}

int Div(int a, int b) {
	return Mul(a, power(b, mod - 2));
}
int P(int n, int r) {
	if (n < r || n < 0 || r < 0) return 0;
	return Div(F[n], F[n - r]);
}

int C(int n, int r) {
	if (n < r || n < 0 || r < 0) return 0;
	int ret;
	ret = Div(F[n], Mul(F[n - r], F[r]));
	return ret;
}
int H(int n, int r) {
	if (n == 0 && r == 0) return 1;
	return C(n + r - 1, r);
}
int K[64];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int A[300010];
    rep(i, N) cin >> A[i];
    
    int sum = 0;
    rep(i, N) {
        int num = A[i];
        int cnt = 0;
        while(num > 0) {
            K[cnt] += num % 2;
            num /= 2;
            cnt++;
        }
    }
    //rep(i, 4) cout << "*" << K[i] << endl;
    int ans = 0;
    rep(i, N - 1) {
        int cnt = 0;
        rep(j, 62) {
            if (A[i] % 2 == 1) {
                ans = (ans + Mul((1LL << j), (N - i) - K[j])) % mod;
            } else {
                ans = (ans + Mul((1LL << j), K[j])) % mod;
            }
            K[j] -= A[i] % 2;
            A[i] /= 2;
            //cout << i << " "<< ans << endl;
        }
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main(void) {
  int a, b, c;
  int ans = 0;
  cin >> a >> b >> c;

  ans += (a != b) ? 1 : 0;
  ans += (b != c) ? 1 : 0;
  ans += (c != a) ? 1 : 0;
  ans += (a == b && b == c) ? 1 : 0;

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
     
int main(void)
{
int i;
char s[100],sa[200],p[100];
scanf("%s\n%s\n",s,p);
char pa[strlen(p)];
strcpy(pa,p);
strcpy(sa,s);
for (i=0;i < strlen(s);i++){
sa[strlen(s)+i] = s[i];
}
if (strstr(sa,pa) != NULL)
{
printf("Yes\n");
}else{
printf("No\n");
}
return 0;
}


Measured memory_bytes: 2076
#include <bits/stdc++.h>
using namespace std;
#define ALL(A) (A).begin(),(A).end()
#define ll long long
const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

int main(void){
	int N;
	cin >> N;
	cout << N*N*N << endl;
}

Measured memory_bytes: 764