akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;

typedef long long LL;
const int MOD = 1e9+7;

void solve(){
	vector<string> table{"hon","pon","bon"};
	vector<int> dp={1,1,0,2,0,0,1,0,1,0};
	int n;
	cin>>n;
	cout<<table[dp[n%10]]<<endl;
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug" << x << endl;
using namespace std;

int main(){
    int x,y;
    while(cin >> x >> y){
        if(x == y && x == 0) break;
        if(x <= y) cout << x << ' ' << y << endl;
        else if(x > y) cout << y << ' '  << x << endl;
    }
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>

int N, M, Q;
std::vector<int> a;
std::vector<int> b;
std::vector<int> c;
std::vector<int> d;
int max_sum = 0;

void calc(std::vector<int>& A, int index) {
	if (index == A.size()) {
		int sum = 0;
		for (int i = 0; i < Q; ++i) {
			if (A[b[i] - 1] - A[a[i] - 1] == c[i]) {
				sum += d[i];
			}
		}
		if (sum > max_sum) {
			max_sum = sum;
		}
	}
	else {
		for (int i = index ? A[index - 1] : 1; i <= M; ++i) {
			A[index] = i;
			calc(A, index + 1);
		}
	}
}

int main()
{
	std::cin >> N >> M >> Q;
	for (int i = 0; i < Q; ++i) {
		int _a, _b, _c, _d;
		std::cin >> _a >> _b >> _c >> _d;
		a.push_back(_a);
		b.push_back(_b);
		c.push_back(_c);
		d.push_back(_d);
	}

	std::vector<int> A(N);
	calc(A, 0);

	std::cout << max_sum << std::endl;

	return 0;
}

Measured memory_bytes: 3616
#include<stdio.h>
int main() {
	int a, b, c;
	bool ans = true;
	scanf("%d%d%d", &a, &b, &c);
	if (a > c) {
		ans = false;
	}
	if (b < c) {
		ans = false;
	}
	if (ans == true) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
}

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

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [list(map(int, list(input().strip('\n')))) for _ in range(n)]

        # ???(North)??????(West)?????????(NorthWest)?????????(NorthEast) ????????????????????????1???????????£?¶???????????????????????????????
        N = [[0] * n for _ in range(n)]
        W = [[0] * n for _ in range(n)]
        NW = [[0] * n for _ in range(n)]
        NE = [[0] * n for _ in range(n)]
        N_max = 0               #  ???????????????????????§?????£?¶???????1????????§?????°
        W_max = 0
        NW_max = 0
        NE_max = 0

        for i in range(n):
            for j in range(n):
                c = data[i][j]  #  ????????????data[i][j]?????????????????§???????????§?????????????¨???¶

                # North??????
                ni = i - 1
                if ni < 0:
                    N[i][j] = c
                    if N[i][j] > N_max:
                        N_max = N[i][j]
                else:
                    if c == 1:
                        N[i][j] = N[ni][j] + 1
                        if N[i][j] > N_max:
                            N_max = N[i][j]
                    else:
                        N[i][j] = 0

                # West??????
                nj = j - 1
                if nj < 0:
                    W[i][j] = c
                    if W[i][j] > W_max:
                        W_max = W[i][j]
                else:
                    if c == 1:
                        W[i][j] = W[i][nj] + 1
                        if W[i][j] > W_max:
                            W_max = W[i][j]
                    else:
                        W[i][j] = 0

                # North West??????
                ni = i - 1
                nj = j - 1
                if ni < 0 or nj < 0:
                    NW[i][j] = c
                    if NW[i][j] > NW_max:
                        NW_max = NW[i][j]
                else:
                    if c == 1:
                        NW[i][j] = NW[ni][nj] + 1
                        if NW[i][j] > NW_max:
                            NW_max = NW[i][j]
                    else:
                        NW[i][j] = 0

                # North East??????
                ni = i - 1
                nj = j + 1
                if ni < 0 or nj >= n:
                    NE[i][j] = c
                    if NE[i][j] > NE_max:
                        NE_max = NE[i][j]
                else:
                    if c == 1:
                        NE[i][j] = NE[ni][nj] + 1
                        if NE[i][j] > NE_max:
                            NE_max = NE[i][j]
                    else:
                        NE[i][j] = 0

        print(max(N_max, W_max, NW_max, NE_max))



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

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

#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define EPS (1e-7)
#define INF 1e9

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int vx[]={0,1,0,-1};
int vy[]={1,0,-1,0};

int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,1,-1,1,-1};

const ll mod=1000000000+7;
const int MAX_N=1000;

int main(){
	int n;
	cin>>n;
	int a[n];
	pii p[n];
	REP(i,n){
		cin>>a[i];
		p[i]=pii(a[i],i);
	}
	sort(p,p+n);
	p[0]=pii(0,p[0].second);
	for(int i=1;i<n;i++){
		p[i]=pii(p[i-1].first+1,p[i].second);
	}
	REP(i,n){
		a[p[i].second]=p[i].first;
	}

	int count=0;
	REP(i,n){
		if(abs(a[i]-i)%2==0)continue;
		else count++;
	}
	cout<<count/2<<endl;
	return 0;
}

Measured memory_bytes: 1408
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

global score

def dfs(graph, nd, d):
    global score
    max_depth = 0
    if score[nd] != -1:
        return score[nd] + 1
    if len(graph[nd]) == 0:
        score[nd] = 0
        return 1
    for adj in graph[nd]:
        max_depth = max(max_depth, dfs(graph, adj, d + 1))

    #if max_depth > score[nd]:
    score[nd] = max_depth
    return score[nd] + 1


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    sys.setrecursionlimit(100000)
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    global score
    score = {}
    for i in range(1, N+1):
        graph[i] = []
        score[i] = -1
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)

    for i in range(1, N + 1):
        dfs(graph, i, 0)
    max_score = 0
    for i in range(1, N + 1):
        max_score = max(max_score, score[i])
    print max_score
##        q = [i]
##        d = 0
##        while 1:
##            if len(q) <= 0:
##                score[i] = d
##                break
##            nd = q.pop()
##            if score[nd] != -1:
##                score[i] = d + score[nd]
##                break
##            for adj in graph[nd]:
##                if score[nd] + 1 > score[adj]:
##                    q.append(adj)
##                    score[adj] = score[nd] + 1
##                else:







if __name__ == '__main__':
    main()


Measured memory_bytes: 118348
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        n: usize, m: usize,
        a: [i64; n],
    }
    let sum = a.iter().sum::<i64>();
    let mut cnt = 0;
    for i in 0..n {
        if a[i] * 4 * m as i64 >= sum {
            cnt += 1;
        }
    }
    puts!("{}\n", if cnt >= m { "Yes" } else { "No" });
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
#include<iostream>
#include<algorithm>

using namespace std;

int main(void){

  int n=123456*2+1;
  int p[n];
  
  fill(p,p+n,1);
  p[0]=p[1]=0;

  for(int i=2;i*i<n;i++)
    if(p[i]==1)
      for(int j=i*i;j<n;j+=i)
	p[j]=0;

  for(int i=1;i<n;i++)p[i]+=p[i-1];

  while(cin >> n, n){
    cout << p[n*2]-p[n] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 4008
N,M = map(int,input().split())
X,Y,Z = [],[],[]
for i in range(N):
    x,y,z = map(int,input().split())
    X.append(x)
    Y.append(y)
    Z.append(z)

Sign = [[1,1,1],[1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]
Ans = []

for sign in Sign:
    T = []
    for i in range(N):
        T.append(X[i]*sign[0] + Y[i]*sign[1] + Z[i]*sign[2])
    T.sort(reverse=True)
    ans = 0
    for i in range(M):
        ans += T[i]
    Ans.append(ans)

print(max(Ans))




Measured memory_bytes: 3188
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using large = long long;
constexpr int N_max = 200'000;
constexpr int mod = 998'244'353;

static large memo[N_max + 1];

struct Robot {
    int x, d;
    struct Removal {
        Robot *begin;
        Robot *end; // one-past-last
    } removal;
};

static large solve(const Robot *const robots, const Robot *const end) {
    if (robots == end) {
        return 1;
    }
    auto cnt = end - robots;
    if (memo[cnt] >= 0)
        return memo[cnt];

    large ans = 0;

    // activate (and remove)
    {
        large c = solve(robots->removal.end, end);
        ans += c;
        if (ans >= mod)
            ans -= mod;
    }
    // not activate
    {
        large c = solve(robots + 1, end);
        ans += c;
        if (ans >= mod)
            ans -= mod;
    }

    memo[cnt] = ans;
    return ans;
}

int main() {
    for (auto &m : memo)
        m = -1;

    int n;
    cin >> n;
    auto robots = vector<Robot>(n);
    for (int i = 0; i < n; i++) {
        cin >> robots[i].x >> robots[i].d;
    }
    sort(robots.begin(), robots.end(), [](auto &a, auto &b) { return a.x < b.x; });
    robots.push_back(Robot());
    robots[n].x = 2'100'000'000;
    robots[n - 1].removal.begin = &robots[n - 1];
    robots[n - 1].removal.end = &robots[n - 1] + 1;

    for (int i = n - 2; i >= 0; i--) {
        auto *r1 = &robots[i];
        r1->removal.begin = r1;
        r1->removal.end = r1 + 1;

        int x_limit = r1->x + r1->d;

        // check chain reactions
        auto *r2 = r1 + 1;
        while (r2->x < x_limit) {
            robots[i].removal.end = r2->removal.end;
            r2 = r2->removal.end - 1;
            x_limit = max(x_limit, r2->x + r2->d);
            r2++;
        }
    }

    cout << solve(robots.data(), robots.data() + n);
    return 0;
}


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

int main() {
	int x;

	for(int i=0; i<10000; i++) {
		cin >> x;
		if(x == 0) {
			break;
		}
		cout << "Case " << i+1 << ": " << x << endl;
	}

	return 0;
}


Measured memory_bytes: 3088
#include <cstdio>
const int MAXN = 2e5+1;
int L, R;
char S[MAXN];
bool F[MAXN*2], f;
int main()
{
	int N, K, i, T;
	scanf("%d%d%s", &N, &K, S);
	for(i=0; i<N; ++i)
		F[i] = S[i] == 'B';
	L = 0, R = N;
	if (K <= 2*N)
		T = K;
	else if(N&1 && K&1)
		T = 2*N+1;
	else
		T = 2*N;
	for(i=0; i<T; ++i)
		if(f ^ F[L])
			f = !f, ++L, F[R++] = f;
		else
			F[L] ^= 1;
	for(i=L; i<R; ++i)
		putchar((F[i]^f) ? 'B' : 'A');
	puts("");
}

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

using namespace std;

struct vw_pair {
    int v, w;
    vw_pair(int v,int w) : v(v), w(w) {};
};

typedef pair<int, int> ii;
typedef vector <ii> vii;
typedef vector<int> vi;
typedef vector <string> vs;
typedef vector <vi> vvi;
typedef vector <vector<vw_pair>> adj_list;
typedef vector <bool> vb;
typedef long long ll;
typedef unsigned long long ull;

int find_LIS(vi& a) {
    int n = a.size();
    vi L, PL;
    L.push_back(a[0]);
    int max_pos = 0;
    for (int i=1;i<n;++i) {
        int k = upper_bound(L.begin(),L.end(),a[i]) - L.begin();
        if (k == L.size()) {
            L.push_back(a[i]);
        } else if (L[k] > a[i]) {
            L[k] = a[i];
        }
    }
    return L.size();
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, xx;
    cin >> n;
    vi a(n);
    for (int i=0;i<n;++i) {
        cin >> a[i];
        a[i] = -a[i];
    }
    int color = 0;
    cout << find_LIS(a) << "\n";
    return 0;
}

Measured memory_bytes: 1276
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
#include <queue>
#include <stack>
#include <utility>
#include <stdio.h>
#include <unistd.h>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)
#define itrep(itr, base) for (auto itr = base.begin(); itr != base.end(); itr++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define PI 3.14159265359

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const int mod = 1000000007;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  ll a;
  string b;
  cin >> a >> b;
  if (b.find(".") != -1) b.erase(b.begin() + b.find("."));
  P((a * stoi(b)) / 100);
  return 0;
}


Measured memory_bytes: 3644
#include<iostream>
#include<string>
using namespace std;
int main()
{
	int n,i,j,k,a=0,b=0;
	string s;
	cin>>s;
	for(i=0;i<3;i++)
	{
		if(s[i]=='A')a++;
		else b++;
	}
	if(a==3||b==3)
	{
		printf("No");
	}
	else printf("Yes");
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cout <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cout <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}
#define jeb() fflush(stdout);

using namespace std;

char s[1234567];
int mod2[1234567];

int main() {
	make(n);
	scanf("%s", s);
	VI v;
	FOR(i,0,n) {
		v.pb(s[i] -'1');
	}
	int m = n-1;
	FOR(i,0,m) {
		mod2[i] = 1;
		int cpm = m;
		int cpi = i;
		while (cpi != 0) {
			if (cpi%2 == 1 && cpm %2 == 0) {
				mod2[i] = 0;
				break;
			}
			cpi /= 2; cpm /= 2;
		}
	}
	mod2[m] = 1;
	int jeden = 0;
	FOR(i,0,n) if (v[i] == 1) jeden = 1;
	int parity = 0;
	FOR(i,0,n) {
		parity = (parity + v[i] * mod2[i]) % 2;
	}
	if (parity) {
		printf("1\n"); return 0;
	}
	if (jeden) {
		printf("0\n");
		return 0;
	}

	parity = 0;
	FOR(i,0,n) {
		parity = (parity + (v[i]/2) * mod2[i]) % 2;
	}
	if (parity) {
		printf("2\n");
		return 0;
	}
	printf("0\n");
}





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

using namespace std;

#define int long long
#define pb push_back
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)

signed main () {
  int n;
  cin >> n;
  vector<int> a(n);
  int tmp;
  REP(i, n) {
    cin >> tmp;
    a[i] = tmp;
  }
  int ans = 0;
  REP(i, n) {
    if(a[a[i]-1] == i + 1) ans++;
  }
  cout << ans / 2 << endl;
}

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

using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using pii = pair<ll, ll>;

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << '(' << p.first << ", " << p.second << ')';
  return os;
}

int main() {
  // ios::sync_with_stdio(false);
  ll n, m, a, b;
  cin >> n >> m;
  vvi g = vvi(n);
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<pii> sign = vector<pii>(n, make_pair(-1, 1e6));
  sign[0] = make_pair(0, 0);

  queue<ll> q;

  q.push(0);
  bool able = true;
  while (!q.empty()) {
    ll p = q.front();
    q.pop();
    ll previous = p;
    ll score = sign[p].second;

    if (score > n) {
      break;
    }
    // cerr << "previous:" << previous << endl;
    // cerr << "score:" << score << endl;
    // cerr << p << endl;
    for (ll i : g[previous]) {
      if (i == 0) continue;
      if (sign[i].first == -1) {
        // cerr << '\t' << i;
        // cerr << '\t' << sign[i] << endl;
        sign[i].first = previous;
        sign[i].second = score + 1;
        // cerr << '\t' << "updated:" << sign[i] << endl;
        q.push(i);
      }
    }
  }

  // cerr << "test" << endl;
  for (int i = 1; able && i < n; i++) {
    // cerr << sign[i] << endl;
    if (sign[i].first == -1) {
      able = false;
    }
  }

  if (able) {
    cout << "Yes" << endl;
    for (int i = 1; i < n; i++) {
      cout << sign[i].first + 1 << endl;
    }
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 13732
#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;

int main(){
    char a[1000][1000];
    int H, W, cnt = 0;
    string str;
    cin >> H >> W;
    for(int i = 1; i <= H; ++i){
        cin >> str;
        for(int j = 1; j <= W; ++j){
            a[i][j] = str[j-1];
        }
    }

    
for(int m = 0; m < 100; ++m){
    for(int i = 1; i <= H; ++i){
        for(int k = 1; k <= W; ++k){
            if(a[i][k] == '.') ++cnt;
        }
        if(cnt == W){
            for(int j = i; j < H; ++j){
                for(int l = 1; l <= W; ++l){
                    a[j][l] = a[j+1][l];
                }
            }
            --H;
        }
        cnt = 0;
    }
    for(int i = 1; i <= W; ++i){
        for(int k = 1; k <= H; ++k){
            if(a[k][i] == '.') ++cnt;
        }
        if(cnt == H){
            for(int j = i; j < W; ++j){
                for(int l = 1; l <= H; ++l){
                    a[l][j] = a[l][j+1];
                }
            }
            --W;
        }
        cnt = 0;
    }
}

    for(int i = 1; i <= H; ++i){
        for(int j = 1; j <= W; ++j){
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 384
//的場梨沙★担当
//結城晴★副担当
//日野茜★副担当
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string.h>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stdio.h>


using namespace std;

int main(void) {
    int N,M,C;
    cin>>N>>M>>C;
    vector<int>B(M);
    for(int i=0;i<M;i++)cin>>B[i];


    vector<vector<int>>A(N,vector<int>(M));
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>A[i][j];
        }
    }

    int ans=0;
    for(int i=0;i<N;i++){
        int c=0;
        for(int j=0;j<M;j++){
            c+=A[i][j]*B[j];
        }

        if(c+C>0){
            ans++;
        }
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ls( s) (s&(-s))
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =    1e9+7;
ll n,m;
ll go(ll x)
{
	ll ans=0;
	for(int i=1;i<=x;i++)
	{
		ll a;
		cin>>a;
		(ans+=(2*i-x-1)*a)%=mod;
	}
	return ans;
}
int main()
{  fast
cin>>n>>m;
ll x=go(n)%mod;
ll y=go(m)%mod;
cout<<x*y%mod;
}


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

class card{
public:
	char suit;
	int value;
};

void swapCard(card arr[], int i, int j){
	card temp;
	temp.value = arr[j].value;
	temp.suit = arr[j].suit;
	arr[j].value = arr[i].value;
	arr[j].suit = arr[i].suit;
	arr[i].value = temp.value;
	arr[i].suit = temp.suit;
}


void bubbleSort(card arr[], int n){
	card temp;
	for(int i = 0; i < n; i ++){
		for(int j = n - 1; j > i; j--){
			if(arr[j].value < arr[j - 1].value){
				swapCard(arr,j ,j-1);
			}
		}
	}
}

void selectionSort(card arr[], int n){
	card temp;
	int min_i;
	for(int i = 0; i < n; i++){
		min_i = i;
		for(int j = i; j < n; j++){
			if(arr[j].value < arr[min_i].value){
				min_i = j;
			}
		}
		if(min_i != i){
			swapCard(arr,i , min_i);
		}
	}
}

void printCardArr(card arr[], int n){
	for(int i = 0;i < n; i++){
		cout << arr[i].suit << arr[i].value;
		if(i != n - 1){
			cout << ' ';
		}
	}
	cout << endl;
}

int isSameCardArray(card arr1[], card arr2[], int n){
	for(int i = 0; i < n; i++){
		if(arr1[i].value != arr2[i].value || arr1[i].suit != arr2[i].suit){
			return 0;
		}
	}
	return 1;
}

int main(){
	int n;
	card arr1[36];
	card arr2[36];

	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> arr1[i].suit >> arr1[i].value;
		arr2[i].suit = arr1[i].suit;
		arr2[i].value = arr1[i].value;
	}

	bubbleSort(arr1,n);
	printCardArr(arr1, n);
	cout << "Stable" << endl;

	selectionSort(arr2, n);
	printCardArr(arr2, n);

	if(isSameCardArray(arr1, arr2, n)){
		cout << "Stable" << endl;
	}else{
		cout << "Not stable" << endl;
	}

	return 0;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define MOD 1000000007

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 (b<a) { a=b; return 1; } return 0; }

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	int asum = 0;
	rep(i,n) {
		cin >> a[i];
		asum += a[i];
	}
	int q;
	cin >> q;
	vector<int> m(q);
	rep(i,q) cin >> m[i];
	rep(i,q) {
		if(m[i] > asum) {
			cout << "no" << endl;
			continue;
		}
		else if(m[i] == asum) {
			cout << "yes" << endl;
			continue;
		}
		for(int j=0; j < (1<<n); j++) {
			int sum=0;
			rep(k,n) {
				if(1 & (j >> k)) sum += a[k];
			}
			if(sum == m[i]) {
				cout << "yes" << endl;
				break;
			}
			if(j == (1<<n)-1) cout << "no" << endl;
		}
	}

  return 0;
}


Measured memory_bytes: 3092
#include<vector>
#include<map>
#include<set>
#include<iostream>
using namespace std;
#define df 0
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long int li;
int dx[4]={+1, 0,-1, 0};
int dy[4]={ 0,+1, 0,-1};

// print_item
template<typename T>
void print_item(T x) {cout << x;}
// pair 型の print (map 含む)
template<typename F,typename S>
void print_item(pair<F,S> x);
void print(auto& vec,string str="");
// 二重vector 型
template<typename T>
void print(vector<vector<T>>& vec,string str="");

int main(){
  if(df) printf("*debug mode*\n");
  int n; cin >>n;
  li ans; cin >>ans; ans--;
  int k=2;
  rep(i,n-1){
    int a; cin >>a;
    if(a==k){
      k++; continue;
    }
    ans+=(a-1)/k;
  }
  cout << ans;
}

// pair 型の print (map 含む)
template<typename F,typename S>
void print_item(pair<F,S> x) {
  printf("(");
  print_item(x.first);
  printf(",");
  print_item(x.second);
  printf(")");
}
void print(auto& vec,string str){
  if(str!="") cout << str << ":";
  for(auto x: vec) {print_item(x); cout << " ";}
  cout << endl;
}
// 二重vector 型
template<typename T>
void print(vector<vector<T>>& vec,string str){
  if(str!="") cout << str << ":\n";
  int n=vec.size();
  rep(i,n){
    print(vec.at(i),(string){(char)(i+'0')});
  }
}


/// confirm df==0 ///


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int box[1000000];
void soinsuu(ll n){
  ll hoge=n;
    for(ll i=2;i*i<=n;i++){
        while(hoge%i==0){
            box[i]++;
            hoge/=i;    
        }
        if(hoge==1)break;
    } 
}
int main(){
    ll n,p;
    cin>>n>>p;
    if(n==1){
        cout<<p<<endl;
        return 0;
    }
    soinsuu(p);
    ll ans=1;
    for(ll i=2;i*i<=p;i++){
        while(box[i]>=n){
            ans*=i;
            box[i]-=n;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    double a[n];
    double s=0;
    for(int i=0; i<n; i++){
        cin>>a[i];
        s+=(1/a[i]);
    }
    s=(1/s);
    printf("%.14lf\n", s);
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define ll long long
#define ull unsigned long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define lowbit(x) (x& -x)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define eps 1e-18
#define maxn 200010
inline ll read(){ll tmp=0; char c=getchar(),f=1; for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1; for(;'0'<=c&&c<='9';c=getchar())tmp=(tmp<<3)+(tmp<<1)+c-'0'; return tmp*f;}
inline ll power(ll a,ll b){ll ans=0; for(;b;b>>=1){if(b&1)ans=ans*a%mod; a=a*a%mod;} return ans;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void swap(int &a,int &b){int tmp=a; a=b; b=tmp;}
using namespace std;
ll a[maxn];
int n;
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read()-i;
	sort(a+1,a+n+1);
	ll ans=0,b=a[n/2+1];
	for(int i=1;i<=n;i++)
		ans+=abs(a[i]-b);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1664
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  if (n == 1 || m == 1) {
    cout << 1;
  } else {
    cout << (n * (ll)m + 1) / 2 << '\n';
  }

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=int(b); i++)
#define per(i,a,b) for (int i=(a); i>=int(b); i--)
using namespace std;
typedef long long LL;

const int maxn = 100005;
LL pre[maxn], suf[maxn], x[maxn], v[maxn], ans, best, C;
int n;

int main() {
	scanf("%d%lld", &n, &C);
	rep (i, 1, n) scanf("%lld%lld", &x[i], &v[i]);
	rep (i, 1, n) pre[i] = pre[i-1] + v[i];
	per (i, n, 1) suf[i] = suf[i+1] + v[i];
	per (i, n, 1) {
		ans = max(ans, best + pre[i] - x[i]);
		best = max(best, 2 * (x[i] - C) + suf[i]);
		ans = max(ans, x[i] - C + suf[i]);
	}
	best = 0;
	rep (i, 1, n) {
		ans = max(ans, best + suf[i] + x[i] - C);
		best = max(best, - 2 * x[i] + pre[i]);
		ans = max(ans, - x[i] + pre[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3328
import static java.util.Arrays.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	static final int MOD = 100000;
	void solve() {
		int N = sc.nextInt();
		N = N * N;
		int M = sc.nextInt();
		int S = sc.nextInt();
		if ((N | M | S) == 0) return;
		int[][] dp = new int[N+1][S+1];
		dp[0][0] = 1;
		for (int m = 1; m <= M; m++) {
			for (int n = N-1; n >= 0; n--) {
				for (int j = m; j <= S; j++) {
					dp[n+1][j] += dp[n][j-m];
					if (dp[n+1][j] >= MOD) dp[n+1][j] -= MOD;
				}
			}
		}
		out.println(dp[N][S]);

	}

	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}

Measured memory_bytes: 20152
#include <cstdio>

int main(){
  int n = 3;
  int p[n];
  scanf("%d %d %d", &p[0], &p[1], &p[2]);
  int min_time = 200;
  for (int i = 0; i < n; i++) {
    if (min_time > p[i] + p[(i+1) % n]) {
      min_time = p[i] + p[(i+1) % n];
    }
  }
  printf("%d\n", min_time);
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int MAX = 1e5 + 5;
ll cnt[MAX];

void solve() {
    int n;
    cin >> n;
    fori (i, 0, n) {
        int x; cin >> x; cnt[x]++;
    }
    ll total = 0;
    fori (i, 0, MAX) {
        total += 1LL * i * cnt[i];
    }
    int q;
    cin >> q;
    while (q--) {
        int b, c;
        cin >> b >> c;
        ll b_cnt = cnt[b];
        total -= 1LL * b * b_cnt;
        total += 1LL * c * b_cnt;
        cnt[b] = 0;
        cnt[c] += b_cnt;
        cout << total << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
        solve();
    return 0;
}



Measured memory_bytes: 4388
#include <iostream>
#include <cassert>
#include <string>
#include <cctype>

using namespace std;

string S;
size_t cur=0;

int digit() {
  assert(isdigit(S[cur]));
  int n = S[cur] - '0';
  cur++;
  return n;
}

int number() {
  int n = digit();
  while(cur < S.size() && isdigit(S[cur])) {
    n = n*10 + digit();
  }
  return n;
}

int expression();

int factor() {
  if (S[cur] != '(') return number();
  cur++;
  int n = expression();
  assert(S[cur] == ')');
  cur++;
  return n;
}

int term() {
  int a = factor();
  while (cur < S.size() && (S[cur] == '*' || S[cur] == '/')) {
    char op = S[cur++];
    int b = factor();
    if (op == '*') a *= b;
    else a /= b;
  }
  return a;
}

int expression() {
  int a = term();
  while (cur < S.size() && (S[cur] == '+' || S[cur] == '-')) {
    char op = S[cur++];
    int b = term();
    if (op == '+') a += b;
    else a -= b;
  }
  return a;
}

int main() {
  int N;
  cin >> N;
  for (int i=0; i<N; i++) {
    cur = 0;
    cin >> S;
    S.resize(S.size() - 1); // '='?????????
    cout << expression() << endl;
  }
}

// accepted!
#if 0
???????????????pdf?????????????????????????????§?????¨?????§45?????????
?????°??????????????¨??§?????????????????????????°?????????????????????¨???????????§?????????
#endif

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

int main(){
    int n,m,l;
    long long x[100][100],y[100][100],z[100][100];
    cin>>n>>m>>l;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>x[i][j];
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<l;j++){
            
            cin>>y[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<l;j++){
            z[i][j]=0;
            for(int k=0;k<m;k++){
                z[i][j]+=x[i][k]*y[k][j];
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<l;j++){
            if(j)cout << " ";
            cout<<z[i][j];
        }
        cout<<endl;
    }
    return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;
using lint=long long;

const long long INF=1LL<<61;

class starry_sky_tree{
	int n;
	vector<lint> dat1,dat2;

	void add(int l,int r,int a,int b,int u,lint val){
		if(b<=l || r<=a) return;
		if(l<=a && b<=r){ dat1[u]+=val; return; }

		add(l,r,a,(a+b)/2,2*u+1,val);
		add(l,r,(a+b)/2,b,2*u+2,val);

		dat2[u]=max(dat2[2*u+1]+dat1[2*u+1],dat2[2*u+2]+dat1[2*u+2]);
	}

	lint query_max(int l,int r,int a,int b,int u){
		if(b<=l || r<=a) return -INF;
		if(l<=a && b<=r) return dat1[u]+dat2[u];

		lint res1=query_max(l,r,a,(a+b)/2,2*u+1);
		lint res2=query_max(l,r,(a+b)/2,b,2*u+2);
		return max(res1,res2)+dat1[u];
	}

public:
	starry_sky_tree(int N){
		for(n=1;n<N;n*=2);
		dat1.assign(2*n,0);
		dat2.assign(2*n,0);
	}

	void add(int l,int r,lint val){ add(l,r,0,n,0,val); }
	void update_max(int x,lint val){
		lint tmp=query_max(x,x+1);
		if(tmp<val) add(x,x+1,val-tmp);
	}

	lint query_max(int l,int r){ return query_max(l,r,0,n,0); }
};

int main(){
	int n,m; scanf("%d%d",&n,&m);
	vector<int> l(m),r(m),val(m);
	rep(i,m) scanf("%d%d%d",&l[i],&r[i],&val[i]), r[i]++;

	vector<vector<int>> L(n+2),R(n+2);
	rep(i,m){
		L[l[i]].emplace_back(i);
		R[r[i]].emplace_back(i);
	}

	starry_sky_tree SS(n+2);
	SS.add(1,n+2,-INF);

	rep(x,n+2){
		for(int i:R[x]) SS.add(0,l[i],-val[i]);
		for(int i:L[x]) SS.add(0,l[i], val[i]);
		SS.update_max(x,SS.query_max(0,x));
	}
	printf("%lld\n",SS.query_max(0,n+2));

	return 0;
}


Measured memory_bytes: 32640
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

int extgcd(int a, int b, int& x, int& y) {
	int d = a;
	if(b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	 } else {
		 x = 1; y = 0;
	 }
	return d;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

  int a, b, x, y;
  cin >> a >> b;
  int d = extgcd(a, b, x, y);
  cout << x << " " << y << endl;
}




Measured memory_bytes: 3204
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<algorithm>
#include<list>
#include<cmath>
#include<iomanip>
#include<queue>
#include<functional>
#include<climits>
#include<iterator>
#include<unordered_map>

using namespace std;

const double pi=4*atan(1.0);

int mod=1000000007;

int main() {
	int n,m;
	cin>>n>>m;
	vector<int> Coins(m);
	for(auto& val:Coins)
		cin>>val;

	sort(begin(Coins),end(Coins));

	vector<vector<int>> dp(m,vector<int>(n+1));
	for(int i=0;i<m;++i){
		dp[i][0]=0;
	}

	for(int i=0;i<n+1;++i){
		dp[0][i]=i;
	}

	for(int i=1;i<m;++i){
		for(int j=1;j<min(Coins[i],n+1);++j){
			dp[i][j]=dp[i-1][j];
		}
		for(int j=Coins[i];j<n+1;++j){
			dp[i][j]=min(dp[i-1][j],dp[i][j-Coins[i]]+1);
		}
	}

	cout<<dp[m-1][n]<<endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 7004
#include <iostream>
#include <string>
#include <set>

int main() {
  std::string S;
  long K;

  std::cin >> S;
  std::cin >> K;

  std::string substrbufs[5];
  size_t buf_idx=0;

  std::set<std::string> words;

  for (auto const& c : S) {
    if (buf_idx<5) {
      for (size_t i=0; i<buf_idx+1; i++) {
        substrbufs[i].push_back(c);
      }
    } else {
      substrbufs[buf_idx%5].erase();
      for (size_t i=buf_idx; i<buf_idx+5; i++) {
        substrbufs[i%5].push_back(c);
      }
    }

    for (size_t i=0; i<5; i++) {
      words.insert(substrbufs[i]);
    }

    buf_idx++;
  }

  size_t count=0;
  for (auto const& w : words) {
    if (count == K) {
      std::cout << w << std::endl;
      break;
    }
    count++;
  }

  return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <map>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
	int N, M, H[100000];
	cin >> N >> M;
	map<int, int> mii;
	rep(i, N) {
		int tmp;
		cin >> tmp;
		H[i] = tmp;
	}
	rep(i, M) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		tmp1--;tmp2--;
		if (H[tmp1] >= H[tmp2]) mii[tmp2] = 1;
		if (H[tmp1] <= H[tmp2]) mii[tmp1] = 1;
	}
	
	int ans = 0;
	rep(i, N) {
		if (mii[i] == 0) ++ans;
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 8672
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) v.begin(), v.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int n, m; cin >> n >> m;
  vector<string> v1(n), v2(m);
  rep(i, n) cin >> v1[i];
  rep(i, m) cin >> v2[i];
  int k = 0;bool f = true;
  for(int i = 0; i < n-m+1; ++i){
    for(int j = 0; j < n-m+1; j++){
      bool f = true;
      for(int k = 0; k < m; k++){
        for(int l = 0; l < m; l++){
          if(v1[i+k].at(j+l) != v2[k].at(l))f = false;
        }
      }
      if(f){
        cout <<"Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  system("pause");
}

Measured memory_bytes: 504
#include <iostream>
using namespace std;
#define MAX 200000
#define SENTINEL 2000000000
typedef long long llong;

int L[MAX/2+2],R[MAX/2+2];

llong merge(int A[],int n,int left,int mid,int right) {
  int n1=mid-left;
  int n2=right-mid;
  for (int i=0; i<n1; i++) {
    L[i]=A[left+i];
  }
  for (int i=0; i<n2; i++) {
    R[i]=A[mid+i];
  }
  L[n1]=R[n2]=SENTINEL;
  int i=0;
  int j=0;
  llong cnt=0;
  for (int k=left; k<right; k++) {
    if (L[i]<=R[j]) {
      A[k]=L[i++];
    } else{
      A[k]=R[j++];
      cnt+=n1-i;
    }
  }
  return cnt;
}
llong mergeSort(int A[],int n,int left,int right) {
  int mid;
  llong v1,v2,v3;
  if (left+1<right) {
    mid=(left+right)/2;
    v1=mergeSort(A,n,left,mid);
    v2=mergeSort(A,n,mid,right);
    v3=merge(A,n,left,mid,right);
    return v1+v2+v3;
  } else{
    return 0;
  }
}
int main() {
  int A[MAX];
  int n;
  cin>>n;
  for (int i=0; i<n; i++) {
    cin>>A[i];
  }
  llong ans=mergeSort(A,n,0,n);
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 4640
// AOJ 2129: Text Justification
// 2017.11.9 bal4u@uu

#include <stdio.h>
#include <string.h>

int s[1002], dp[1002];

char buf[20], *bp;
int getint()
{
	int n = 0;
	while (*bp >= '0') n = (n<<3) + (n<<1) + (*bp++ & 0xf);
	return n;
}

int main()
{
	int n, w, i, j, t, ans;
	int cno = 0;

	while (1) {
		fgets(bp=buf, 20, stdin);
		n = getint(), bp++, w = getint();
		if (!n && !w) break;

		for (s[0] = 0, i = 1; i <= n; i++) {
			fgets(bp=buf, 10, stdin);
			s[i] = s[i-1] + getint();
		}
		memset(dp, 0x55, sizeof(dp)); dp[0] = 0;
		for (i = 1; i <= n; i++) for (j = 0; j < i; j++) {
			t = s[i] - s[j] - w;
			if (t < 0) t = -t;
			if (dp[j] + t < dp[i]) dp[i] = dp[j] + t;
		}
		for (ans = 0x7fffffff, i = 0; i < n; i++) {
			t = s[n] - s[i] - w;
			if (t > 0) dp[i] += t;
			if (ans > dp[i]) ans = dp[i];
		}
		printf("Case %d: %d\n", ++cno, ans);
	}
	return 0;
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> P1;
typedef pair<P, P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i, x) for (long long i = 0; i < x; i++)
#define repn(i, x) for (long long i = 1; i <= x; i++)
#define SORT(x) sort(x.begin(), x.end())
#define ERASE(x) x.erase(unique(x.begin(), x.end()), x.end())
#define POSL(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin())
#define POSU(x, v) (upper_bound(x.begin(), x.end(), v) - x.begin())
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rrepn(i, n) for (int i = ((int)(n)); i > 0; --i)
#define SZ(x) ((int)(x).size())
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 (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
vector<pair<string, P>> vec;
// vector<vector<int>> data(3, vector<int>(4));

int main() {
    int D;
    cin >> D;
    vector<int> c(26);
    rep(i, 26) cin >> c[i];
    vector<vector<int>> s(D, vector<int>(26));
    rep(i, D) rep(j, 26) cin >> s[i][j];

    vector<int> t(D);
    // rep(i, D) {
    //     cin >> t[i];
    //     t[i]--;
    // }

    rep(i, D) {
        int now = 0;
        rep(j, 26) {
            if (now <= s[i][j]) {
                now = s[i][j];
                t[i] = j;
            }
        }
    }

    auto scoring = [&]() {
        vector<int> last(26);
        int score = 0;
        rep(i, D) {
            score += s[i][t[i]];
            last[t[i]] = i + 1;
            int m = 0;
            rep(j, 26) m += c[j] * (i + 1 - last[j]);
            score -= m;
            // cout << score << endl;
        }
        return score;
    };

    int score = scoring();
    srand((unsigned int)time(NULL));
    rep(i, 320000) {
        int d = rand() % D;
        int q = rand() % 26;
        int old = t[d];
        t[d] = q;
        int now = scoring();
        if (score > now) {
            t[d] = old;
        } else {
            score = now;
        }
    }

    rep(i, D) { cout << t[i] + 1 << endl; }
    return 0;
}


Measured memory_bytes: 3684
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define pii pair<int,int>
#define vvi vector<vector<int> >
#define vpi vector<pii>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define INF 0x7fffffff
#define LINF 0x7fffffffffffffff
#define MOD 1000000007
#define mod 998244353
#define lowbit(x) x&(-x)
#define HS 173LL
using namespace std;
int read()
{
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))
		ch=getchar();
	while(isdigit(ch))
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
string s,t;
int main()
{
	cin>>s>>t;
	int ans=1e9;
	for(int i=0;i<=(int)s.size()-(int)t.size();i++)
	{
		int cnt=0;
		for(int j=0;j<t.size();j++)
			if(s[i+j]!=t[j])
				++cnt;
		ans=min(ans,cnt);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3632
data Circle = Circle { _loc :: (Double, Double), _r :: Double }
distance :: Circle -> Circle -> Double
distance (Circle (x0,y0) _) (Circle (x1,y1) _) = sqrt $ (x0-x1)^2 + (y0-y1)^2

solve :: Circle -> Circle -> Int
solve c0@(Circle _ r0) c1@(Circle _ r1)
    | r0+r1 < d = 0
    | d+r1 < r0 = 2
    | d+r0 < r1 = -2
    | otherwise = 1
    where d = distance c0 c1

parseLn :: [Double] -> (Circle, Circle)
parseLn [xa,ya,ra,xb,yb,rb] = (Circle (xa,ya) ra , Circle (xb,yb) rb)

main = getContents >>=
    mapM_ (print . uncurry solve . parseLn . map read . words) . tail . lines

Measured memory_bytes: 4388