akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<algorithm> // sort
#include<map> // pair
#include<cmath>
#include <cstring>
using namespace std;
using ll = long long;
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 rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
const ll mod = 1e9+7;
const int INF = 1e9;
const ll INFLONG = 1e18;
int main(){
  ll n,m;
  cin >> n >> m;
  ll a[m],b[m];
  rep(i,m){
    cin >> a[i];
  }
  sort(a,a+m);
  REP(i,1,m){
    b[i-1] = a[i]-a[i-1];
  }
  ll sum=0;
  sort(b,b+m-1);
  rep(i,m-n){
    sum += b[i];
  }
  cout << sum;
}


Measured memory_bytes: 1792
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
#define double long double
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
#define eps 1e-12 
//priority_queue<int,vector<int>, greater<int> > q2;

struct UnionFind {
	VI par, s;
	UnionFind(int N) :par(N), s(N) {
		REP(i, N)par[i] = i;
		REP(i, N)s[i] = 1;
	}
	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}
	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		if (!(same(x, y)))s[ry] += s[rx];
		par[rx] = ry;
	}
	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
	int size(int x) {
		return s[root(x)];
	}
};

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

	int N; cin >> N;
	int M; cin >> M;
	UnionFind uni(N);
	REP(i, M) {
		int a, b; cin >> a >> b;
		a--, b--;
		uni.unite(a, b);
	}
	int ans = 0;
	REP(i, N)chmax(ans, uni.size(i));




	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 12668
#include <cmath>
#include <iostream>
using namespace std;
double xa, ya, xb, yb, xc, yc, xd, yd;
int main() {
	while(cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd) {
		xb -= xa, yb -= ya;
		xd -= xc, yd -= yc;
		if(abs(xb * xd + yb * yd) < 1.0e-12) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}


Measured memory_bytes: 3068
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define int long long
#define INF 10000000
using namespace std;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
signed main(){
    int k,n;
    cin >> n >> k;
    int ans = n%k;
    if(ans == 0) cout << 0 << endl;
    else cout << 1 << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import deque
import numpy as np

# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx, sy):
    # すべての点を INF で初期化
    d = [[float("-inf")] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        #if p[0] == gx and p[1] == gy:
        #    break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("-inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    a = np.max(d) 
    return a

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
ans = 1

for x in range(n):
    for y in range(m):
        sx = x
        sy = y
        if maze[sx][sy] == "#":
            continue
        A = bfs(sx, sy)
        ans = max(A, ans)
print(int(ans))

Measured memory_bytes: 26812
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#ifndef print
#define print(...)
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;
//const int mod=998244353;
const int mod = 1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk = clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) { uniform_int_distribution<int> uid(0, lim - 1); return uid(rang); }
int powm(int a, int b) { int res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }

int dp[5005];
int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.precision(10); srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	int n, m;
	cin>>n>>m;
	dp[0] = 1;
	for (int i = 2; i <= n; ++i) {
		int mm = min(i - 1, n + 2 - i);
		for (int j = 0; j <= n; ++j)
			dp[j] = (dp[j] + (j - mm >= 0 ? dp[j - mm] : 0ll)) % m;
	}
	int ans = 0;
	for (int i = 0; i <= n - 1; ++i) {
		ans += (n - i) * dp[i] % m;
		ans %= m;
	}
	cout << ans;
}

Measured memory_bytes: 384
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort
#include <map> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

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

    vector <int> d(n);
    REP(i,n)cin >> d[i];

    ll res = 0;

    REP(i,n)
    {
        for(int j = i + 1; j < n; ++j)
        {
            res += d[i]*d[j];
        }
    }

    cout << res << endl;
    return 0;    
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s,t,r;
	int i,j,m;
	cin>>s;
	cin>>t;
	cin>>i;
	cin>>j;
	cin>>r;
	if(r==s)i--;
	if(r==t)j--;
	cout<<i<<" "<<j;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=505;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    stack< char > stk;
    string s;cin>>s;
    ll ans = 0;
    for(ll i=0;i<s.size();i++){
        if(s[i]=='T'){
            if(stk.empty())ans++;
            else stk.pop();
        }
        else{
            stk.push(s[i]);
        }
    }

    cout<<ans + stk.size();
}



Measured memory_bytes: 720
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

vector<int> boat[200005];
bool node[200005] = { false };
int N, M;

bool bfs(int cur, int target) {
	int level = 0;
	queue<int> q;
	q.push(cur);
	node[cur] = true;
	int last = cur;
	while (!q.empty()) {
		int c = q.front();
		q.pop();
		if (c == target) return true;
		for (int i = 0; i < boat[c].size(); i++) {
			if (node[boat[c][i]] == false) {
				q.push(boat[c][i]);
				node[boat[c][i]] = true;
			}
		}
		if (c == last) {
			level++;
			if (level >= 3) {
				return false;
			}
			if (!q.empty()) last = q.back();
		}
	}
	return false;
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int one, two;
		cin >> one >> two;
		boat[one].push_back(two);
		boat[two].push_back(one);
	}
	if (bfs(1, N)) cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 12528
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int v;
	if(s[0]=='S'&&s[1]=='U')
		v=0;
	if(s[0]=='M')
		v=1;
	if(s[0]=='T'&&s[1]=='U')
		v=2;
	if(s[0]=='W')
		v=3;
	if(s[0]=='T'&&s[1]=='H')
		v=4;
	if(s[0]=='F')
		v=5;
	if(s[0]=='S'&&s[1]=='A')
		v=6;
	cout<<7-v;
} 

Measured memory_bytes: 256
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,a,b = m()

po = n // (a+b)

poo = n % (a+b)

if poo <= a:
    print(a*po + poo)
else:
    print(a*po + a)





Measured memory_bytes: 38484
#include <bits/stdc++.h>
#define pii pair<long long,long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int w,h,n;
long long x,y;
long long dp[3007],ca=1;
vector <pii> pr;
long long MOD=1e9+7;
long long gt[200007],lop[200007];
long long po(long long a,long long b){
    if(b==1) return a%MOD;
    long long z=po(a,b/2);
    if(b%2==0) return (z*z)%MOD;
    else return (((z*z)%MOD)*a)%MOD;
}
long long cal(long long a,long long b){
    if(a>b) return 0;
    return (((gt[b]*lop[a])%MOD)*lop[b-a])%MOD;
}
int main(){
    ios_base::sync_with_stdio(0);
    gt[0]=1;
    lop[0]=1;
    for(int i=1;i<=200006;i++){
        ca=(ca*i)%MOD;
        gt[i]=ca;
        lop[i]=po(gt[i],MOD-2);
    }
    cin>>w>>h>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        pr.pb(mp(x,y));
    }
    sort(pr.begin(),pr.end());
    pr.pb(mp(w,h));
    for(int i=0;i<=n;i++){
        //cout<<i;
        x=pr[i].fi;
        y=pr[i].se;
        dp[i]=cal(x-1,x+y-2);
        for(int j=0;j<i;j++){
            long long px=pr[j].fi,py=pr[j].se;
            if(y<py) continue;
            dp[i]=(dp[i]-((dp[j]*cal(x-px,x-px+y-py))%MOD)+MOD)%MOD;
        }
    }
    cout<<dp[n];
}


Measured memory_bytes: 3584
#encoding: utf-8

import sys

N, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(N)]

def dfs(idx, a, b, c):
    if idx == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else sys.maxsize
    
    ret0 = dfs(idx + 1, a, b, c)
    ret1 = dfs(idx + 1, a + l[idx], b, c) + 10
    ret2 = dfs(idx + 1, a, b + l[idx], c) + 10
    ret3 = dfs(idx + 1, a, b, c + l[idx]) + 10
    return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))


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

int main(void)
{
  long long N, A, B;
  cin >> N >> A >> B;

  if (A == 0 || A + B == 0)
  {
    cout << A << endl;
    return 0;
  }

  if (A > N)
  {
    cout << N << endl;
    return 0;
  }
  if (B > N)
  {
    cout << A << endl;
    return 0;
  }

  long long count = 0;
  long long set = A + B;
  long long setCount = N / set;
  N -= setCount * set;
  count += setCount * A;

  while (N > 0)
  {
    if (N - A >= 0)
    {
      N -= A;
      count += A;
    }
    else
    {
      count += N;
      N -= A;
    }

    if (N - B > 0)
    {
      N -= B;
    }
    else
    {
      break;
    }
  }

  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

#define Max 10000000

int main(void)
{
    int n, i, j, k, num, count, min = Max;
    int m[101], p[101][101] = {0};

    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        scanf("%d %d", &m[i], &m[i+1]);
    }


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

    
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n-i; j++) {
            count = i + j;
            min = p[j][j] + p[j+1][count] + m[j] * m[j+1] * m[count+1];;
            for (k = j; k < count; k++) {
                num = p[j][k] + p[k+1][count] + m[j] * m[k+1] * m[count+1];
                if (num < min) {
                    min = num;
                }
            }
            p[j][count] = min;
        }  
    }

    printf("%d\n", p[1][n]);
    return 0;
}


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

using i64 = int64_t;

constexpr int MAX_V = 110;
constexpr i64 INF = 1e12;

// 辺を表す構造体 (行き先, 容量, 逆辺)
struct edge {
    i64 to, cap, rev;
};

vector<edge> G[MAX_V]; // グラフの隣接リスト表現
int level[MAX_V];           // sからの距離
int iter[MAX_V];            // どこまで調べ終わったか

// fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge(int from, int to, i64 cap) {
    G[from].push_back((edge){to, cap, (int)G[to].size()});
    G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
}

// sからの最短距離をBFSで計算する
void bfs(int s) {
    memset(level, -1, sizeof(level));
    std::queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (int i = 0; i < G[v].size(); i++) {
            edge &e = G[v][i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

// 増加パスをDFSで探す
i64 dfs(int v, int t, i64 f) {
    if (v == t)
        return f;
    for (int &i = iter[v]; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            i64 d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// sからtへの最大流を求める
i64 max_flow(int s, int t) {
    i64 flow = 0;
    for (;;) {
        bfs(s);
        if (level[t] < 0)
            return flow;
        memset(iter, 0, sizeof(iter));
        i64 f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
}

int main(){
    int n;
    cin >> n;
    i64 sum = 0;
    for(int i=1;i<=n;++i){
        i64 a;
        cin >> a;
        if(a > 0){
            sum += a;
            add_edge(0, i, 0);
            add_edge(i, n+1, a);
        }else{
            add_edge(0, i, -a);
            add_edge(i, n+1, 0);
        }
        for(int j=i*2;j<=n;j+=i){
            add_edge(i, j, INF);
        }
    }
    i64 loss = max_flow(0, n+1);
    cout << sum - loss << endl;

    return 0;
}


Measured memory_bytes: 256
/**
 @Author -> saurabhP
**/

#include <iostream>
#include <map>

#define print(arr, n) for(int i = 0; i < n; i++) std::cout << arr[i] << " ";
#define read(arr, n) for(int i = 0; i < n; i++) std::cin >> arr[i];

typedef long long int lld;

using namespace std;

void fast(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0); std::cout.tie(0);
}

int main(){
    // fast();
    map <int, int> mp;

    int n, t;
    cin >> n;

    while(n--){
        cin >> t;

        if(!mp.count(t)) mp[t] = 0;
        mp[t]++;
    }

    string ans = "YES";

    for(auto it: mp){
        if(it.second > 1){
            ans = "NO";
            break;
        }
    }

    cout << ans;

    return 0;
}


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

using namespace std;

int main(){
  long long int dp[10005];
  int a[1005],b[1005];
  int h,n;
  cin>>h>>n;
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
  }
  for(int i=0;i<h;i++)
    dp[i]=9000000000;
  dp[h]=0;
  for(int i=h;i>0;i--){
    for(int j=0;j<n;j++){
      if(i-a[j]<0) 
        dp[0]=min(dp[0],dp[i]+b[j]);
      else
        dp[i-a[j]]=min(dp[i-a[j]],dp[i]+b[j]);
    }
  }
  cout<<dp[0]<<endl;
  return 0;
}

Measured memory_bytes: 384
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

const inf = int(1e9) + 1

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}

func main() {
	var n int
	fmt.Scan(&n)
	r := make([]int, n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := 0; i < n; i++ {
		r[i] = nextInt(sc)
	}
	minv, maxv := r[0], -inf
	for i := 1; i < len(r); i++ {
		maxv = max(maxv, r[i]-minv)
		minv = min(minv, r[i])
	}
	fmt.Println(maxv)
}



Measured memory_bytes: 5416
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

int INF = 0x3f3f3f3f;
int mod = 1e9+7;
int MAXN = 12345;
double eps = 1e-7;

int dcmp(double a, double b) 
{
    return (a - b < eps)? -1: (a - b >= eps);
}

int main(int argc, char **argv)
{
    ios::sync_with_stdio(false);
    int n, m;

    scanf("%d", &n);

    printf("%d\n", n*n*n);

    return 0;
}


Measured memory_bytes: 256
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
a = [0]
b = [0]
for i in range(N):
  a.append(a[i]+A[i])
for i in range(M):
  b.append(b[i]+B[i])

ans, j = 0, M
for i in range(N+1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i+j)
print(ans)

Measured memory_bytes: 47320
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <map>
#include <algorithm>
#include <math.h>
#include <iostream>     // std::cout, std::fixed
#include <iomanip>
#include<queue>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <iostream>
#include <sstream>
#include <time.h>
using namespace std;
typedef long long ll;

int main () {
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<ll> a(n);
    vector<ll> b(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    ll pos=0;
    ll neg=0;
    for(int i=0;i<n;i++)
    {
        if(b[i]-a[i]>0)
            pos+=((b[i]-a[i])/2);
        if(b[i]-a[i]<0)
            neg+=(-(b[i]-a[i]));
    }
    if(pos>=neg)
        cout<<"Yes";
    else
        cout<<"No";
    
    return 0;
}


Measured memory_bytes: 384
import java.util.*;
public class Main 
{
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(a < b)
		{
			System.out.println("a < b");
		}
		else if(a > b)
		{
			System.out.println("a > b");
		}
		else
		{
			System.out.println("a == b");
		}
	}
}

Measured memory_bytes: 17172
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e9
const int MAX_N=100;
const int MAX_W=100;
const int MOD=1000000007;

int dp[1001][1001];

int main(){
    string s1,s2;
    cin>>s1>>s2;
    for(int i=0;i<s1.length()+1;i++) dp[i][0]=i;
    for(int j=0;j<s2.length()+1;j++) dp[0][j]=j;
    for(int i=1;i<s1.length()+1;i++){
        for(int j=1;j<s2.length()+1;j++){
            int cost=s1[i-1]==s2[j-1]?0:1;
            dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+cost);
        }
    }
    cout<<dp[s1.length()][s2.length()]<<endl;
}


Measured memory_bytes: 7052
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<cmath>
#include<cstring>
#include<set>
#include<climits>
#include<deque>
#include<iomanip>
#include<utility>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define all(a) a.begin(),a.end()
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define size(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
#define S 21 
llfor;
const ll mod=1000000007;
/*pi*/const double pi=acos(-1);
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll ans=1;rep(i,0,n){ans*=x;}return ans;}
/*階乗*/ll fact(ll x){ll ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)*fact(n-r)/fact(r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
/*Fibonacci数列*/ll fib(ll x){ll fibo[x+10];fibo[0]=1;fibo[1]=1;fibo[2]=1;rep(i,3,x+1)fibo[i]=fibo[i-1]+fibo[i-2];return fibo[x];}
/*桁数*/ll dig(ll n){ll d=0,tmp=n;while(tmp!=0){tmp/=10;d++;}return d;}
/*行列のコピー*/void matcpy(ll a[S][S],ll b[S][S]){ll t=i;rep(i,0,S)rep(j,0,S)b[i][j]=a[i][j];/*(aをbに)*/i=t;}
/*行列のリセット*/void matrst(ll a[S][S]){ll t=i;rep(i,0,S)rep(j,0,S)a[i][j]=0;i=t;}
/*行列の2乗*/void matpow(ll a[S][S]){ll ans[S][S];matrst(ans);ll t=i,k;rep(i,0,S)rep(j,0,S)rep(k,0,S)ans[i][j]+=a[i][k]*a[k][j];matcpy(ans,a);i=t;}
/*行列の乗算*/void matmul(ll a[S][S],ll b[S][S], ll as[S][S]){ll t=i,k;matrst(as);rep(i,0,S)rep(j,0,S)rep(k,0,S)as[i][j]+=a[i][k]*b[k][j];i=t;}
//ll ans=0;
////////////////////////////////////////////////////////////
int main(){
 ll n;
 cin>>n;
 ll a[n+10],b[n+10];
 ll as=0,bs=0;
 rep(i,0,n){
  cin>>a[i];
  as+=a[i];
 }
 rep(i,0,n){
  cin>>b[i];
  bs+=b[i];
 }
 ll cnt=bs-as;
 if(cnt<0){
  pn;
  return 0;
 }
 ll ac=0,bc=0;
 rep(i,0,n){
  if(a[i]<b[i]&&a[i]%2!=b[i]%2){
   b[i]++;
   bc++;
   ac+=abs(a[i]-b[i])/2;
  }
  else if(a[i]<b[i]){
   ac+=abs(a[i]-b[i])/2;
  }
  else if(b[i]<a[i]){
   bc+=(a[i]-b[i]);
  }
  if(ac>cnt||bc>cnt){
   pn;
   return 0;
  }
 // cout<<i<<" "<<ac<<" "<<bc<<endl;
 }
 py;
return 0;}


Measured memory_bytes: 3716
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

even,odd = map(int,input().split())
ans = 0
if even>=2:
    ans += comb(even,2)
if odd>=2:
    ans += comb(odd,2)
print(ans) 

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


int main() {
int N,ans=0,min=300000;
  cin>>N;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin>>a.at(i);
  }
  for(int i=0;i<N;i++){
    if(a.at(i)<min){
      ans++;
      min=a.at(i);
    }
  }
  cout<<ans;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque



import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    q = deque()
    q.append(1)
    d = {}
    d[1] = 0
    prev = {}
    while q:
        u = q.popleft()
        for v in g[u]:
            if v in d:
                continue
            d[v] = d[u] + 1
            prev[v] = u
            q.append(v)
    print('Yes')
    return [prev[i] for i in range(2, N+1)]


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(*slv(N, M, AB), sep='\n')


if __name__ == '__main__':
    main()


Measured memory_bytes: 157872
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin >> s;
  int ans = 0;
  if (s[0]=='+') ans++;
  else ans--;
  if (s[1]=='+') ans++;
  else ans--;
  if (s[2]=='+') ans++;
  else ans--;
  if (s[3]=='+') ans++;
  else ans--;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;

#define gcu getchar_unlocked
#define pcu putchar_unlocked
#define _T template <typename T>
#define _HT template <typename H, typename... T>
#define _il inline
#define _in _il int in
#define _sc _il bool scan
_T T in(int c){T n=0;bool m=false;if(c=='-')m=true,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0');return m?-n:n;} //&&c<='9'
_in() {return in<int>(gcu());}
_T T scan(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_sc(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#endif
_HT _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _vo _il void out
#define _vl _il void outl
_vo(const char *s){while(*s)pcu(*s++);}
_vo(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_vo(string s){for(char c:s)pcu(c);}
#endif
_T _vo(T n){static char buf[20];char *p=buf;
	if(n<0)pcu('-'),n*=-1;if(!n)*p++='0';else while(n)*p++=n%10+'0',n/=10;
	while (p!=buf)pcu(*--p);}
_vl(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _vo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);outl();}
#endif
_HT _vo(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _vl(T&&... t){out(move(t)...);outl();}

int test(double a) {
	return a >= 1.1 ? 0 : a >= 0.6 ? 1 : a >= 0.2 ? 2 : 3;
}

int main() {
	double l, r;
	vector<int> L(4), R(4);
	while (scanf("%lf %lf", &l, &r) != EOF) {
		L[test(l)]++;
		R[test(r)]++;
	}
	for (int i = 0; i < 4; i++)
		outl(L[i], ' ', R[i]);
}


Measured memory_bytes: 2696
fun main(args: Array<String>) {
    abc043b()
}

fun abc043b() {
    val s = readLine()!!

    val sb = StringBuilder()
    s.forEach { c ->
        when (c) {
            'B' -> if (sb.isNotEmpty()) sb.deleteCharAt(sb.lastIndex)
            else -> sb.append(c)
        }
    }

    println(sb)
}


Measured memory_bytes: 33528
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 998244353;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

///////////////////////////


int main() {
	ll N;
	cin >> N;

	ll sd;
	repn(i, N+1) {
		if (i*(i + 1) / 2 > N) { sd = i; break; }
	}
	
	repn(i, sd) {
		if (i == sd * (sd + 1) / 2 - N) { continue; }
		cout << i << endl;
	}
	
	system("PAUSE");
}


Measured memory_bytes: 504
n,m=map(int,input().split())

#Union-Find
par=[-1 for i in range(n)]

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

xyz=[]
for i in range(m):
    a=[int(j) for j in input().split()]
    xyz.append([a[0]-1,a[1]-1,a[2]%2])
    if root(a[0]-1)!=root(a[1]-1):
        connect(a[0]-1,a[1]-1)
ans=0
for i in range(n):
    if par[i]<0:
        ans+=1
print(ans)

Measured memory_bytes: 21948
import bisect
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
B = [int(_) for _ in stdin.readline().rstrip().split()]
C = [int(_) for _ in stdin.readline().rstrip().split()]
A.sort()
C.sort()
ans = 0
for b in B:
  ans += bisect.bisect_left(A, b) * (N - bisect.bisect_right(C, b))
print(ans)

Measured memory_bytes: 23232
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 標準入力からデータを読み込む準備
Scanner sc= new Scanner(System.in);
int w = sc.nextInt();
int n = sc.nextInt();
int[] values = new int[w];
for(int i= 0; i< values.length; i++) {
values[i] = i+ 1;
}
for(int i= 0; i< n; i++) {
String str= sc.next();
String[] ab = str.split(",");
int a = Integer.parseInt(ab[0]) -1;
int b = Integer.parseInt(ab[1]) -1;
// aとbを使ってvaluesを操作しよう
	int c=0;
	c=values[a];
	values[a]=values[b];
	values[b]=c;
}
// valuesを出力しよう
for(int i= 0; i< values.length; i++) {
	System.out.println(values[i]);
}
}
}

Measured memory_bytes: 26108
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int a = 0;
		for (int i = 0; i < N; i++) {
			a += (i+1);
		}
		System.out.println(a);

	}

}


Measured memory_bytes: 9804
#include<iostream>
#include<sstream>
#include <cmath>

using namespace std;

int main(){
  long long x;
  cin>>x;
  long long i=x;
  long long flag=0;
  while(true){
    flag=0;
    for(long long j=2; j<=sqrt(i); j++){
      if(i%j==0){
        flag++;
        break;
      }
    }
    if(flag==0){
      break;
    }
    i++;
  }
  cout<<i<<endl;
  return 0;
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define UNIQUE(c) sort(ALL(c)), c.erase(unique(ALL(c)), c.end())

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

#define INF 1 << 29

template <typename T>
struct BipartiteMatching {
  struct Edge {
    int to, rev;
    T cap;
    Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap) {}
  };

  typedef vector<Edge> Edges;
  vector<Edges> G;
  int V, source, sink;
  vector<int> level, iter;

  BipartiteMatching(int V1, int V2) {
    V = V1 + V2 + 2, source = V - 2, sink = V - 1;
    G.resize(V);
    add_sink_source(V1, V2);
  }

  void add_edge(int from, int to) {
    G[from].emplace_back(to, G[to].size(), 1);
    G[to].emplace_back(from, (int)G[from].size() - 1, 0);
  }

  void add_sink_source(int V1, int V2) {
    for (int i = 0; i < V1; i++) add_edge(source, i);
    for (int i = V1; i < V1 + V2; i++) add_edge(i, sink);
  }

  void bfs(int source) {
    level.assign(V, -1);
    queue<int> que;
    que.emplace(source);
    level[source] = 0;
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      for (int i = 0; i < (int)G[v].size(); i++) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[e.to] < 0) {
          level[e.to] = level[v] + 1;
          que.emplace(e.to);
        }
      }
    }
  }

  T dfs(int v, int sink, T flow) {
    if (v == sink) return flow;
    for (int &i = iter[v]; i < (int)G[v].size(); i++) {
      Edge &e = G[v][i];
      if (e.cap > 0 && level[v] < level[e.to]) {
        T d = dfs(e.to, sink, min(e.cap, flow));
        if (d > 0) {
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }

  T run() {
    T flow = 0;
    while (true) {
      bfs(source);
      if (level[sink] < 0) return flow;
      iter.assign(V, 0);
      T f;
      while ((f = dfs(source, sink, INF)) > 0) {
        flow += f;
      }
    }
  }
};


int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N; cin >> N;
  BipartiteMatching<int> bp(N, N);
  vector<pair<int, int>> red(N), blue(N);
  REP(i, N) {
    int a, b; cin >> a >> b;
    red[i] = make_pair(a, b);
  }
  REP(i, N) {
    int c, d; cin >> c >> d;
    blue[i] = make_pair(c, d);
  }

  REP(i, N) REP(j, N) {
    int a, b, c, d; tie(a, b) = red[i]; tie(c, d) = blue[j];
    if (a < c and b < d) {
      bp.add_edge(i, j + N);
    }
  }

  cout << bp.run() << endl;
  return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

template <typename T>
struct Edge { int src, dst; T cost;
    Edge(int dst, T cost) : src(-1), dst(dst), cost(cost) { }
    Edge(int src, int dst, T cost) : src(src), dst(dst), cost(cost) { }
};
template <typename T> using Edges = vector<Edge<T>>;
template <typename T> using WeightedGraph = vector<Edges<T>>;
template <typename T> using Matrix = vector<vector<T>>;

template <typename T>
vector<T>  bellman_ford(Edges<T> &edges, int V, int s) {
    const T INF = numeric_limits<T>::max();
    vector<T> dist(V, INF); dist[s] = 0;
    vector<T> memo(V);
    for (int i = 0; i < V; i++) {
        for (auto &e: edges) if (dist[e.src] != INF) {
            dist[e.dst] = min(dist[e.dst], dist[e.src] + e.cost);
        }
        memo[i] = dist[V - 1];
    }
    return memo;
}

int main() {
    int N, M; cin >> N >> M;
    Edges<long long> es;
    while (M--) {
        int s, t, d; cin >> s >> t >> d; s--, t--;
        es.emplace_back(s, t, -d);
    }
    auto res = bellman_ford(es, N, 0);
    if (res[N - 2] == res[N - 1]) cout << -res[N - 2] << endl;
    else cout << "inf" << endl;
    return 0;
}

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

const int INF = (1<<31)-1;

struct segtree{
  vector<int> dat;
  int size;
  segtree(int n){
    size = 1;
    while(size<n) size *= 2;
    dat.assign(2*size-1,INF);
  }
  void update(int i,int x){
    i += size - 1;
    dat[i] = x;
    while(i>0){
      i = (i-1)/2;
      dat[i] = min(dat[2*i+1],dat[2*i+2]);
    }
  }
  int query(int a,int b,int k,int l,int r){
    if(b<=l||r<=a) return INF;
    if(a<=l&&r<=b) return dat[k];
    return min(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r));
  }
};

int main(){
  int n,q;
  scanf("%d %d",&n,&q);
  segtree st(n);
  for(int i=0;i<q;i++){
    int cmd,x,y;
    scanf("%d %d %d",&cmd,&x,&y);
    if(cmd==0) st.update(x,y);
    else printf("%d\n",st.query(x,y+1,0,0,st.size));
  }
  return 0;
}

Measured memory_bytes: 3428
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード

    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


n, m = map(int, input().split())
uni = UnionFind(n)
cnt = 0

for i in range(m):
    x, y, _ = map(int, input().split())
    if not uni.isSameGroup(x, y):
        cnt += 1
        uni.Unite(x, y)

print(n - cnt)


Measured memory_bytes: 82008
#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define range(i,a,b) for(int i=a; i<(int)(b); i++)
#define rep(i,b) range(i,0,b)

typedef int Capacity;
struct Edge {
    int src, dst;
    Capacity cap;
    Edge(int src_, int dst_, int cap_) :
        src(src_), dst(dst_), cap(cap_) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<int> Array;
typedef vector<Array> Matrix;

int const inf = 1e9;

template<class Capacity = int> struct FordFulkerson {
    typedef vector<vector<Capacity>> Matrix;
    size_t n;
    Matrix cap, flow;
    vector<bool> vis;
    Capacity res;
    vector<vector<int>> g;
    FordFulkerson(const int s, const int t, const Graph &graph){
        n = graph.size();
        cap.assign(n, Array(n));
        flow.assign(n, Array(n));
        g.assign(n, {});
        res = 0;
        rep(i,n)rep(j,graph[i].size()){
            int u = graph[i][j].src, v = graph[i][j].dst;
            Capacity c = graph[i][j].cap;
            cap[u][v] += c;
            cap[v][u] += c;
            flow[v][u] += c;
            // cap[u][v] = cap[v][u] = graph[i][j].cap;
            // flow[v][u] = graph[i][j].cap;
        }
        rep(i,n)rep(j,n) if(cap[i][j]) g[i].push_back(j), g[j].push_back(i);
        Capacity f = -1;
        while(f) vis.assign(n,false), res += (f = augment(s,t,inf));
    }
    Capacity augment(const int v, const int t, Capacity lim){
        vis[v] = true;
        if(v == t) return lim;
        for(const int &i : g[v]){
            if(vis[i] || flow[v][i] == cap[v][i]) continue;
            Capacity f = augment(i, t, min(lim, cap[v][i] - flow[v][i]));
            flow[v][i] += f;
            flow[i][v] -= f;
            //cout << flow[v][i] << " " << flow[i][v] << endl;
            assert(0 <= flow[v][i]);
            assert(0 <= flow[i][v]);
            if(f) return f;
        }
        return 0;
    }
};

int main(){
    int N,M;
    cin >> N >> M;
    Graph g(N);
    rep(i,M){
        int a,b,c;
        cin >> a >> b >> c;
        g[a].emplace_back(a,b,c);
    }
    cout << FordFulkerson<>(0,N-1,g).res << endl;
}

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

int main(){
   int N,K;
   cin>>N>>K;
   vector<int> H(N);
   long int ans=0;
  
   for(int i=0;i<N;i++){
      cin>>H.at(i);
   }
   
   sort(H.begin(),H.end(),greater<int>());
   
   for(int i=K;i<N;i++){
      ans+=H.at(i);
   }
  
   cout<<ans<<endl;
}

Measured memory_bytes: 1024
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect

def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n = I()
    if n % 1000 == 0:
        print(n % 1000)
    else:
        print(1000 - (n % 1000))
    return


if __name__ == "__main__":
    solve()


Measured memory_bytes: 64784
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <complex>

#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,n) for(int i=0;i<(n); i++)

using namespace std;
typedef long long ll;
const int MAX_N = 110;
const int MAX_V = 100001;
const ll INF = 1LL<<62;

ll dp[MAX_N][MAX_V];
int main(){
cin.tie(0);
ios::sync_with_stdio(0); //この2行はより速度を向上させる
// 追加２, 以降 cin の入力元が 'input.txt' になる
//提出時に消す！！


int N,W;
cin >> N >> W;

vector<ll> w(N),v(N);
rep(i,N) cin >> w[i] >> v[i];

rep(i,MAX_N){
    rep(j,MAX_V){
        dp[i][j]=INF;
    }
}
dp[0][0] = 0;
rep(i,N){
    rep(j,MAX_V){
        if(j-v[i] >= 0){
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]]+w[i]);
        }
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
    }
}
ll ans = 0;
rep(i,MAX_V){
    if(dp[N][i] <= W){
        ans = i;
    }
}
cout << ans << endl;

return 0;
}


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

using namespace std;

int main()
{
	int n;
	cin >> n;
	char ch;
	cin.get(ch);
	for(int i = 0;i < n;i++)
	{
		string str;
		while(1)
		{
			char inch;
			cin.get(inch);
			if(inch == '\n') break;
			str += inch;
		}
		while(1)
		{
			string::size_type idx = str.find("Hoshino");
			if(idx == string::npos) break;
			str[idx + 6] = 'a';
		}
		cout << str << endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
function Main(input) {
  input = input.split("\n");
  num = parseInt(input[0]);
	array = input[1].split(" ");
  array = array.map(el => {
    return parseInt(el);
  })
  var result = 0;
  array.forEach((element, index, array) => {
    if(index+1 === array[element-1]){
      result++;
    }
  })
  console.log(result/2);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 20980
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,ll>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void print() { cout << "\n"; }
template <class T, class... Args> void print(const T &x, const Args &... args) { cout << x << " "; print(args...);}
void debug_out() { cout << "\n"; }
template <class T, class... Args> void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

const ll INF = 1LL<<60;

vector<ll> dijkstra(int n, int s, const vector<vector<pair<int,ll> > > &G) {
  priority_queue<pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > que;
  vector<ll> dist(n, INF);
  dist[s] = 0;
  que.push(pair<ll,int>(0,s));
  while(!que.empty()) {
    pair<ll,int> p = que.top(); que.pop();
    int v = p.second;
    if (dist[v] < p.first) continue;
    for (auto e : G[v]) {
      int to = e.first;
      ll cost = e.second;
      if (dist[to] > dist[v] + cost) {
        dist[to] = p.first + cost;
        que.push(pair<ll,int>(dist[to], to));
      }
    }
  }
  return dist;
}

int get_v(int station, int ginka) { //駅と銀かの枚数から番号を得る(駅1の銀貨が4枚のときは2504)
  return 2500*station + ginka;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n,m;
  ll s;
  cin >> n >> m >> s;
  vector<ll> a(m), b(m), c(n), d(n);
  vector<vector<P> > G(n);
  rep(i,m) {
    int u, v;
    cin >> u >> v >> a[i] >> b[i];
    u--; v--;
    G[u].emplace_back(P(v,i));
    G[v].emplace_back(P(u,i));
  }
  rep(i,n) cin >> c[i] >> d[i];

  vector<vector<P> > cost(n*2505); //各駅に対して2499頂点
  rep(i,n) { //両替の辺を張る
    rep(ginka, 2500) {
      if (ginka + c[i] >= 2500) continue;
      int to = get_v(i, ginka + c[i]);
      cost[get_v(i,ginka)].emplace_back(P(to, d[i])); 
    }
  }
  rep(i,n) { //移動の辺を張る
    for (auto p : G[i]) {
      rep(ginka, 2500) {
        if (ginka - a[p.second] < 0) continue; //足りない
        int to_st = p.first; //行先
        int to = get_v(to_st, ginka-a[p.second]);
        cost[get_v(i,ginka)].emplace_back(P(to, b[p.second])); 
      }
    }
  }
  int start_ginka = min(s, 2499LL);
  vector<ll> dist = dijkstra(n*2500, get_v(0, start_ginka), cost);
  for (int i = 1; i < n; ++i) {
    ll ans = INF;
    rep(ginka,2500) {
      chmin(ans, dist[get_v(i,ginka)]); //到達した中でのmin
    }
    print(ans);
  }
  return 0;
}

Measured memory_bytes: 23732
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    double r;
    cin >> r;
    double p = 3.14159265358979323846;
    printf("%.10f\n", r*2*p);
    return 0;
}


Measured memory_bytes: 3780