akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections.Generic;

namespace Contest
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var p = new ProbremA();
            p.Run();
        }
    }

    internal class ConsoleOutput
    {
        public void Print<T>(T target)
        {
            Console.WriteLine(target.ToString());
        }

        public void PrintList<T>(IEnumerable<T> targets)
        {
            var results = targets.Select(obj => obj.ToString());
            Console.WriteLine(string.Join(" ", results));
        }
    }

    internal class ConsoleInput
    {
        private bool testMode = false;

        private List<string> testInput = new List<string>{
            "10",
        };

        #region Impl

        public int GetInt()
        {
            return int.Parse(Get());
        }

        public List<int> GetIntList()
        {
            return Get().Split(' ').Select(obj => int.Parse(obj)).ToList();
        }

        public string GetString()
        {
            return Get();
        }

        private string Get()
        {
            if (testMode)
            {
                var result = testInput[0];
                testInput.RemoveAt(0);
                return result;
            }

            return Console.ReadLine();
        }

        #endregion Impl
    }

    internal class ProbremA
    {
        private ConsoleInput input = new ConsoleInput();
        private ConsoleOutput output = new ConsoleOutput();

        public void Run()
        {
            int t = input.GetInt();
            int result = t + (t * t) + (t * t * t);
            output.Print(result);
        }
    }

    /*

         internal class ProbremA
        {
            private ConsoleInput input = new ConsoleInput();
            private ConsoleOutput output = new ConsoleOutput();

            public void Run()
            {
            }
        }

     */
}

Measured memory_bytes: 27776
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, x = LI()
L = []
C = []
for _ in range(n):
    c, *A = LI()
    C += [c]
    L += [A]

ans = INF

for i in range(2 ** n):
    B = [0] * m
    ret = 0
    for j in range(n):
        if i >> j & 1:
            ret += C[j]
            for k in range(m):
                B[k] += L[j][k]
    for b in B:
        if b < x:
            break
    else:
        ans = min(ans, ret)

print(-1 if ans == INF else ans)

Measured memory_bytes: 83656
N, K = map(int,input().split())
p = list(map(int, input().split()))
s = [0]
for i in range(N):
  s.append(s[i]+p[i])
num = 0
ans = 0
exp = 0
for i in range(N-K+1):
  sum = s[i+K]-s[i]
  if num<sum: 
    num = sum
    ans = i
for i in range(K):
  exp += (p[ans+i]+1)/2
print(exp)

Measured memory_bytes: 76040
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  for (int i = 0, j = n - 1; i < n; ++i) {
    if (s[i] == 'W') {
      while (j >= i && s[j] == 'W') --j;
      if (i < j) {
        swap(s[i], s[j]);
        ++ans;
      }
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3748
s = str(input())
small = "qazwsxedcrfvtgbyhnujmikolp"
ans = "AC"

if s[0] != "A":
    ans = "WA"
    
if s[1] not in small:
    ans = "WA"
    
if s[-1] not in small:
    ans = "WA"
    
ccount = 0
for i in range(2,len(s)-1):
    if s[i] not in small:
        if s[i] == "C":
            ccount+=1
        else:
            ans = "WA"
            
if ccount != 1:
    ans = "WA"
    
print(ans)

Measured memory_bytes: 3064
#B - Go to Jail
N = int(input())
x =[list(map(int, input().split())) for i in range(N)]
for i in range(N-2):
    if x[i][0] == x[i][1] and x[i+1][0] == x[i+1][1] and x[i+2][0] == x[i+2][1]:
        print("Yes")
        exit()
    else:
        pass
print("No")

Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K;
  cin >> N >> K;
  
  vector<vector<int>> CG(N, vector<int>(2));
  for (int i = 0; i < N; i++) cin >> CG.at(i).at(0) >> CG.at(i).at(1);
  
  vector<vector<int>> gc(10+1);
  for (int i = 0; i < N; i++) gc.at( CG.at(i).at(1) ).push_back( CG.at(i).at(0) );
  
  for (int i = 1; i <= 10; i++) 
    sort( gc.at(i).begin(), gc.at(i).end(), greater<int>() );
  
  for (int i = 1; i <= 10; i++) {
    for (int j = 1; j < gc.at(i).size(); j++) {
      gc.at(i).at(j) += gc.at(i).at(j-1);
    }
  }
  
  vector<int> dp(K+1, 0);
  
  for(int i = 1; i <= 10; i++){
    vector<int> c = dp;
    
    for (int j = 0; j < min(K+1, (int)gc.at(i).size()); j++){
      int val = gc.at(i).at(j) + ( j * ( j + 1 ) );
      
      for(int l = K; l - j - 1 >= 0; l--){    
        c.at(l) = max(c.at(l), dp.at(l-j-1) + val);
      }
      
    }
    
    dp = c;
  }
  cout << dp.at(K) << endl;
  
  return 0;
}


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

const ll INF = 1e18;
const int MX = 2005;

int main() {
  ll n;
  cin >> n;
  ll h[n];
  ll dp[n+2];
  rep(i,n) cin >> h[i];
  rep(i,n) dp[i] = INF;
  dp[0] = 0;
  rep(i,n){
    if(h[i+1] > h[i]){
      dp[i+1] = min(dp[i+1],dp[i] + h[i+1] - h[i]);
    }else{
      dp[i+1] = min(dp[i+1],dp[i] - h[i+1] + h[i]);
    }
    if(h[i+2] > h[i]){
      dp[i+2] = dp[i] + h[i+2] - h[i];
    }else{
      dp[i+2] = dp[i] - h[i+2] + h[i];
    }
  }
  cout << dp[n-1] << endl;
  return 0;
}

Measured memory_bytes: 1792
def fifty_fifty(S: str)->bool:
    m = {}
    for c in S:
        m.setdefault(c, 0)
        m[c] += 1

    return len(m.keys()) == 2 and all(v == 2 for v in m.values())


if __name__ == "__main__":
    S = input()

    ans = fifty_fifty(S)
    print('Yes' if ans else 'No')


Measured memory_bytes: 2940
my$L=+get;
my ($a,$l,$c)=($L,0,0);
while $a>0 {$c+=$a%2;$l++;$a+>=1}
put ($l,$l*2-3+$c);
$a=1;
for (1..^$l) ->$i {
	put ($i,$i+1,0);
	put ($i,$i+1,$a);
	put ($i,$l,$L-=$a) if $L+&$a;
	$a+<=1
}

Measured memory_bytes: 54020
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
const ll mod = 1000000007;

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    

    int ans = a[0];
    rep(i, n) {
        ans = gcd(ans, a[i]);
    }
    
    
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;

int n;
int a[3][3];
int b;
int f[3][3];
int r[3];
int h[3];
int t;
int s;
int ans;
int main()
{
	rep(i,3)rep(j,3)cin>>a[i][j];
	cin>>n;
	rep(kkk,n)
	{
		cin>>b;
		rep(i,3)rep(j,3)
		{
			if(a[i][j]==b)f[i][j]=1;
		}
	}
	rep(i,3)
	{
		rep(j,3)
		{
			r[i]+=f[i][j];
			h[i]+=f[j][i];
			if(r[i]==3)ans=1;
			if(h[i]==3)ans=1;
		}
	}
	rep(i,3)t+=f[i][i];
	rep(i,3)s+=f[2-i][i];
	if(s==3)ans=1;
	if(t==3)ans=1;
	if(ans==1)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	//cout<<(int)((n+1)/2)<<endl;
	return 0;
}

Measured memory_bytes: 256
n, a, b = list(map(int, input().split()))

mod = 10**9 + 7

import time
start = time.time()


# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return pow(x, mod-2, mod)

modinv_table = [-1] * (b+1)
for i in range(1, b+1):
    modinv_table[i] = modinv(i)

end = time.time()
# print("time: ", end - start)

def binomial_coefficients2(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

# (2 ** n - 1) - nCa - nCb
ans = power(2, n) - 1

ans -= (binomial_coefficients2(n, a) + binomial_coefficients2(n, b))
print(ans % mod)


# print(binomial_coefficients2 (5, 2) % mod)


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

int main(){
    double a, b, h, m, ans;
    cin >> a >> b >> h >> m;
    double T = abs((h + m /60) * 2 * M_PI / 12 - m * 2 * M_PI / 60);
    //cout << T << endl;
    //T = M_PI / 2;
    if(T == M_PI){
        cout << fixed << setprecision(11) << a + b << endl;
    }
    else{
        if(T > M_PI){
            T = 2 * M_PI - T;
        }
        ans = a * a + b * b;
        //cout << ans << endl;
        ans -= 2 * a * b * cos(T);
        //cout << ans << endl;
        ans = sqrt(ans);
        cout << fixed << setprecision(11) << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 4196
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int a, b;
    cin >> a >> b;
    if (a == 1) {
        if (b == 2) {
            cout << 3 << endl;
        } else {
            cout << 2 << endl;
        }
    } else if (a == 2) {
        if (b == 1) {
            cout << 3 << endl;
        } else {
            cout << 1 << endl;
        }
    } else if (a == 3) {
        if (b == 1) {
            cout << 2 << endl;
        } else {
            cout << 1 << endl;
        }
    }
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n, m int
	fmt.Scanf("%d %d", &n, &m)
	var wCount [100000]int
	var wFinish [100000]bool
	for i := 0; i < m; i++ {
		var problem int
		var result string
		fmt.Scanf("%d %s", &problem, &result)
		if result == "WA" && wFinish[problem-1] == false {
			wCount[problem-1]++
		}
		if result == "AC" {
			wFinish[problem-1] = true
		}
	}
	cCountSum := 0
	wCountSum := 0
	for i := 0; i < n; i++ {
		if wFinish[i] {
			wCountSum += wCount[i]
			cCountSum++
		}
	}
	fmt.Printf("%d %d\n", cCountSum, wCountSum)
}


Measured memory_bytes: 6400
#include "bits/stdc++.h"
using namespace std;

int main() {
    long long N, M;
    cin >> N >> M;

    if (abs(N - M) > 1) {
        cout << 0 << endl;
    }
    else {
        long long amari = pow(10, 9) + 7;
        long long ans = 1;
        if (N == M) {
            for (int i = 1; i <= N; i++) {
                ans *= i;
                ans %= amari;
            }
            for (int i = 1; i <= M; i++) {
                ans *= i;
                ans %= amari;
            }
            cout << ans * 2 % amari << endl;
        }
        else {
            for (int i = 1; i <= max(N, M); i++) {
                ans *= i;
                ans %= amari;
            }
            for (int i = 1; i <= min(N, M); i++) {
                ans *= i;
                ans %= amari;
            }
            cout << ans << endl;
        }
    }
}

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

#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef long long int lli;
typedef pair<int, int> pi;
typedef pair<lli, int> pii;

vector<lli> flo(lli b)
{
    vector<lli> cn(45);
    for(int i=1; i<43; i++){
        lli x = 1LL<<i;
        lli div = b/x;
        cn[i-1] += div*(x/2);
        lli mod = b%x;
        cn[i-1] += max(0LL, mod-(x/2));
    }
    return cn;
}

int main()
{
    lli a, b;
    cin >> a >> b;
    b++;
    vector<lli> vb = flo(b);
    vector<lli> va = flo(a);
    for(int i=0; i<45; i++){
        vb[i] -= va[i];
    }
    lli ans = 0;
    for(int i=0; i<45; i++){
        if(vb[i]%2){
            ans += 1LL<<i;
        }
    }
    cout << ans << "\n";

    return 0;
}


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


int main(void) {
	long N, i, min = 1000000, j, k, count1 = 0, count2 = 0, cnt1 = 0, cnt2 = 0;
	char C[300000];
	scanf("%d", &N);
	scanf("%s", &C);
	/*for (i = 0; i < N; i++) {
		cnt = 0;
		for (j = 0; j < i; j++) {
			if (C[j] == 'W') {
				cnt++;
			}
		}
		for (k = i + 1; k < N; k++) {
			if (C[k] == 'E') {
				cnt++;
			}
		}
		if (cnt <= min) {
			min = cnt;
		}
	}*/
	for (i = 0; i < N; i++) {
		if (C[i] == 'W') {
			count1++;
		}
		else {
			if (count1 > 0) {
				count1--;
				cnt1++;
			}
		}
	}
	for (i = N - 1; i >= 0; i--) {
		if (C[i] == 'E') {
			count2++;
		}
		else {
			if (count2 > 0) {
				count2--;
				cnt2++;
			}
		}
	}
	if (cnt1 >= cnt2) {
		min = cnt2;
	}
	else {
		min = cnt1;
	}
	printf("%ld",min);

}

Measured memory_bytes: 512
#include <iostream>
#include <string.h>
using namespace std;
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};

int fill(char map[10][10], int y,int x, int c){
	int sum=0;
	int t=map[y][x];
	map[y][x]=c;
	for(int i=0;i<4;i++)
		if(map[y+dy[i]][x+dx[i]] == t){
			sum+=fill(map, y+dy[i], x+dx[i], c);
		}
	return sum+1;
}
int count(char map[10][10], char c){
	char tmp[10][10];
	memcpy(tmp,map,sizeof(tmp));
	if(map[1][1]!=c) return 0;
	return fill(tmp,1,1,0);
}

int solve(char map[10][10], int lim, char c){
	int ret,max=0;
	if(!lim) return count(map, c);
	
	for(char i='1';i<='6';i++){
		char tmp[10][10];
		memcpy(tmp,map,sizeof(tmp));
		if(map[1][1]==i) continue;
		fill(tmp,1,1,i);
		ret=solve(tmp, lim-1, c);
		if(ret>max) max=ret;
	}
	return max;
}

int main(){
	int i,j,h,w;
	char c;
	while(cin>>h>>w>>c,h){
		char map[10][10]={0};
		for(i=1;i<=h;i++)
			for(j=1;j<=w;j++) cin>>map[i][j];
		cout<<solve(map,5,c)<<endl;

	}
}

Measured memory_bytes: 868
import java.util.Scanner;

public class Main {

	static long bignum = 1000000000+7;

	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		long n = sc.nextLong();

		int[] soin = new int[1000010];
		for(int i =0;i<soin.length;i++) {
			soin[i]=0;
		}
		long target = 2;
		int folder = 0;
		boolean bit = false;
		boolean sosu  =true;
		long nn = n;
		long upper = (long)Math.sqrt(n)+3;
		while(target<n+1) {
			if(n%target==0) {
				n = n/target;
				soin[folder]++;
				sosu =false;
				bit  =true;
			}else {
				target++;
				if(bit) {
					folder++;
					bit =false;
				}
				if(target>upper) {
					if(!sosu) {
						soin[folder]++;
					}
					break;
				}
			}
		}
		int counter =0;
		for(int i=0;i<soin.length;i++) {
			int checker =1;
			while(checker<=soin[i]) {
				counter++;
				soin[i]-=checker;
				checker++;
			}
		}
		if(sosu&&(nn!=1)) {
			System.out.println(1);
		}else {
			System.out.println(counter);
		}
	}



	static long divn(int target, int times) {//10_9+7のあまり累乗版
		int sqtimes = (int)Math.sqrt(times);
		long ans = 1;
		for(int i =0;i<sqtimes;i++) {
			ans = (ans * target)%(1000000000+7);
		}
		long holder = ans;
		ans = 1;
		for(int i =0;i<sqtimes;i++) {
			ans = (ans*holder)%(1000000000+7);
		}
		for(int i=0;i<times - sqtimes*sqtimes;i++) {
			ans = (ans * target)%(1000000000+7);
		}
		return ans;
	}

	static long div(long a) {//10_9+7のあまり
		if(a<0)a+=1000000000+7;
		return a%(1000000000+7);
	}

}
/*
class City{
	int order;
	int prefecture;
	int year;
	int number;
	City(int order,int prefecture, int year){
		this.order = order;
		this.prefecture = prefecture;
		this.year = year;
	}
}
*/


Measured memory_bytes: 39780
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
//#define rep2(i, n) for(ll i = 1; i <= ll(n); ++i)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); ++i)
#define rep2(i, k, n) for(ll i = k; i <= ll(n); ++i)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll &b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll &b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
ll num=1, ans=0, cnt=0, sum=0;

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

  ll N, K;
  cin >> N >> K;
  rep2(i, K, N+1) (sum += i*(N+1-i)+1) %= MOD;
  cout << sum << '\n';
  return 0;
}

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

using namespace std;

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

template<class Abel> struct UnionFind {
	vector<int> par;
	vector<int> size;
	vector<int> rank;
	vector<Abel> diff_weight;

	UnionFind(int n) {
		init(n);
	}

	void init(int n) {
		par.resize(n);
		size.assign(n,1);
		rank.resize(n);
		diff_weight.resize(n);
		for (int i = 0; i < n; ++i) par[i] = i; 
	}

	int root(int x) {
		if (par[x] == x) {
			return x;
		} else { 
			int r = root(par[x]);
			size[x] = size[r];
			diff_weight[x] += diff_weight[par[x]];
			return par[x] = r;
		}
	}
	
	int scale(int x) {
		return size[root(x)];
	}

	Abel weight(int x) {
		root(x);
		return diff_weight[x];
	} 

	Abel diff(int x, int y) {
		return weight(y) - weight(x);
	} 

	bool is_same(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y, Abel w = 0) {
		w += weight(x);
		w -= weight(y);
		x = root(x);
		y = root(y);
		if (x == y) return false;
		if (rank[x] < rank[y]) {
			swap(x,y);
			w = -w;
		}
		if (rank[x] == rank[y]) ++rank[x];
		size[x] += size[y];
		par[y] = x;
		diff_weight[y] = w;
		return true;
	}
};
 

int main(){
	int n,q; cin >> n >> q;
	UnionFind<int> uf(n);
	rep(i,q){
		int x,y,z,t; cin >> t;
		if(t){
			cin >> x >> y;
			if(uf.is_same(x,y)) cout << uf.diff(x,y) << endl;
			else cout << "?\n";
		}else{
			cin >> x >> y >> z;
			uf.merge(x,y,z);
		}
	}
}


Measured memory_bytes: 4432
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
vector<P> G[1111];
struct st{
  int prev,curr,dist,pass;
  st(){}
  st(int prev,int curr,int dist,int pass):prev(prev),curr(curr),dist(dist),pass(pass){}
  bool operator<(const st &a) const{
    return dist!=a.dist?dist>a.dist:pass>a.pass;
  }
};
struct Point{
  int x,y;
  Point(){}
  Point(int x,int y):x(x),y(y){}
  Point operator+(Point a){return Point(x+a.x,y+a.y);}
  Point operator-(Point a){return Point(x-a.x,y-a.y);}
  Point operator*(int k){return Point(x*k,y*k);}
};
typedef Point Vector;
int abs(Point a){
  return abs(a.x)+abs(a.y);
}
istream &operator>>(istream &is,Point &p){
  is>>p.x>>p.y;
  return is;
}
int cross(Point a,Point b){
  return a.x*b.y-a.y*b.x;
}
bool izryt(Vector a,Vector b){
  return (cross(a,b)<0);
}

int dp[1111][1111];
int dp2[1111][1111];
signed main(){
  int m,n;
  while(cin>>m>>n,m||n){
    for(int i=0;i<1111;i++) G[i].clear();
    string s[m];
    Point  p[n];
    for(int i=0;i<m;i++){
      cin>>s[i]>>p[i];
    }
    string a[n],b[n];
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];
    string src,dst;
    cin>>src>>dst;
    map<string,int> ms;
    for(int i=0;i<m;i++) ms[s[i]]=i;
    for(int i=0;i<n;i++){
      G[ms[a[i]]].push_back(P(abs(p[ms[b[i]]]-p[ms[a[i]]]),ms[b[i]]));
      G[ms[b[i]]].push_back(P(abs(p[ms[b[i]]]-p[ms[a[i]]]),ms[a[i]]));
    }
    priority_queue<st> q;
    int INF=1LL<<55LL;
    for(int i=0;i<1111;i++)
      for(int j=0;j<1111;j++)
	dp[i][j]=dp2[i][j]=INF;
    for(P e:G[ms[src]]){
      //cout<<e.first<<" "<<e.second<<endl;
      dp[ms[src]][e.second]=e.first;
      dp2[ms[src]][e.second]=2;
      q.emplace(ms[src],e.second,e.first,2);
    }
    int ans=-1;
    while(!q.empty()){
      st pp=q.top();q.pop();
      int prev=pp.prev,curr=pp.curr,dist=pp.dist,pass=pp.pass;
      //cout<<prev<<" "<<curr<<" "<<dist<<" "<<pass<<endl; 
      if(dp[prev][curr]<dist) continue;
      if(dp[prev][curr]==dist&&dp2[prev][curr]<pass) continue;
      if(curr==ms[dst]){
	ans=dp2[prev][curr];
	break;
      }
      //cout<<prev<<" "<<curr<<" "<<dist<<" "<<pass<<endl; 
      Vector c,d;
      for(P e:G[curr]){
	if(e.second==prev) continue;
	c=p[curr]-p[prev];
	d=p[e.second]-p[curr];
	if(izryt(c,d)) continue;
	if(dp[curr][e.second]<dp[prev][curr]+e.first) continue;
	if(dp[curr][e.second]==dp[prev][curr]+e.first&&
	   dp2[curr][e.second]<=dp2[prev][curr]+1) continue;
	dp[curr][e.second]=dp[prev][curr]+e.first;
	dp2[curr][e.second]=dp2[prev][curr]+1;
	q.emplace(curr,e.second,dp[curr][e.second],dp2[curr][e.second]);
      }
    }

    if(ans<0) cout<<"impossible"<<endl;
    else cout<<ans<<endl;
  }
  return 0;
}

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

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

using namespace std;

const int IINF = INT_MAX;
int mini[100][100];

int main(){
  int h,w;
  cin >> h >> w;
  rep(i,h) rep(j,w) mini[i][j] = IINF;
  rep(i,h){
    string s;
    cin >> s;
    rep(j,w) if( s[j] == 'c' ) REP(k,j,w) mini[i][k] = min(mini[i][k],k-j);
  }
  rep(i,h) {
    rep(j,w) {
      if( j ) printf(" ");
      if( mini[i][j] == IINF ) cout << -1;
      else                     cout << mini[i][j];
    } puts("");
  }

  return 0;
}

Measured memory_bytes: 1248
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N;
ll a[101];
int main(){
    cin>>N;
    ll ans=0;
    for(ll i=1;i<=N;i++){
        cin>>a[i];
        if(i%2==1 && a[i]%2==1)ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3588
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <utility>
#define ll long long int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()

using namespace std;

int main(){
	int n;
	cin >> n;
	int maxi = 0;
	int amaxi = 0;
	vector<int> a(n);
	rep(i,0,n) cin >> a[i];
	rep(i,0,n){
		if(maxi<a[i]){
			amaxi = maxi;
			maxi = a[i];
		}else if(amaxi < a[i]){
			amaxi = a[i];
		}
	}
	rep(i,0,n){
		if(maxi == a[i]){
			cout << amaxi << endl;
		}else{
			cout << maxi << endl;
		}
	}
}


Measured memory_bytes: 2432
#include <iostream>

using namespace std;

struct Card
{
	char suit, number;
};

void BubbleSort(struct Card C[], int N)
{
	for (int i = 0; i < N; i++) {
		for (int j = N - 1; j >= i; j--) {
			if (C[j].number < C[j - 1].number) {
				Card t = C[j];
				C[j] = C[j - 1];
				C[j - 1] = t;
			}
		}
	}
}

void SelectSort(struct Card C[], int N)
{
	for (int i = 0; i < N; i++) {
		int minj = i;
		for (int j = i; j < N; j++) {
			if (C[j].number < C[minj].number)
				minj = j;
		}
		Card t = C[i];
		C[i] = C[minj];
		C[minj] = t;
	}
}

bool isStable(struct Card C1[], struct Card C2[], int N)
{
	for (int i = 0; i < N; i++) {
		if (C1[i].suit != C2[i].suit)
			return false;
	}
	return true;
}

int main()
{
	const int MAX = 36;
	int N;
	Card C1[MAX], C2[MAX];

	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> C1[i].suit >> C1[i].number;

	for (int i = 0; i < N; i++) C2[i] = C1[i];

	BubbleSort(C1, N);
	SelectSort(C2, N);

	for (int i = 0; i < N; i++) {
		if (i) cout << ' ';
		cout << C1[i].suit << C1[i].number;
	}
	cout << '\n';
	cout << "Stable" << endl;

	for (int i = 0; i < N; i++) {
		if (i) cout << ' ';
		cout << C2[i].suit << C2[i].number;
	}
	cout << '\n';

	if (isStable(C1, C2, N)) cout << "Stable" << endl;
	else cout << "Not stable" << endl;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {

  int N,M;
  cin >> N >> M;

  vector<vector<int>> s(M,vector<int>(N,0));
  vector<int> p(M);

  for(int i = 0;i < M;i++) {
    int k;
    cin >> k;
    for(int j = 0;j < k;j++) {
      int S;
      cin >> S;
      s.at(i).at(S-1)++;
    }
  }

  for(int i = 0;i < M;i++) {
    cin >> p.at(i);
  }

  int bit = 0,ans = 0;
  for(;bit < (1<<N);bit++) {
    bool can = true;
    for(int i = 0;i < M;i++) {
      int sum = 0;
      for(int j = 0;j < N;j++) {
        if((bit>>j)&1 && s.at(i).at(j)) sum++;
      }
      if(sum % 2 != p.at(i)) {
        can = false;
        break;
      }
    }
    if(can) ans++;
  }

  cout << ans << endl;


}



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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

void solve(){
    long double p;
    i64 n;
    cin >> p >> n;
    vector<vector<pair<int,long double>>> graph(n);
    rep(i,0,n-1){
        int x,y;
        long double c;
        cin >> x >> y >> c;
        --x;
        --y;
        graph[x].push_back(make_pair(y,c));
        graph[y].push_back(make_pair(x,c));
    }

    function<long double(int ,int)> rec1=[&](int u,int par){
        long double res=0;
        for(auto &edge:graph[u]){
            int v=edge.first;
            auto c=edge.second;
            if(v==par) continue;
            res+=(rec1(v,u)+c)*p;
        }
        return res;
    };
    long double sum=rec1(0,-1);
    function<long double(int ,int)> rec2=[&](int u,int par){
        long double res=sum;
        for(auto &edge:graph[u]){
            int v=edge.first;
            auto c=edge.second;
            if(v==par) continue;
            res+=(c+rec2(v,u))*p;
        }
        return res;
    };
    cout << rec2(0,-1) << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Measured memory_bytes: 22348
#include <iostream>

using namespace std;
int main()
{
	string a;
	cin >> a;
	if (a == "RRS" || a == "SRR"){
		cout << "2";
	}
	else if (a == "SSS"){
		cout << "0";
	}
	else if (a == "RRR"){
		cout << "3";
	}
	else cout << "1";
	return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fast_I_O ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr(a,b) for(int i = a; i < b; i++)
const int mod = 1e9+7 , INF = 1e9 ,  mx = 100005 ;
main()
{
    fast_I_O;
    int i,j,n,m,x,y,sum=0,p=0,l=0,k,mn=LLONG_MAX,mx=LLONG_MIN;
    cin>>n;
    for(i=0;i<n;i++) 
    {
        cin>>x>>y;
        if(x==y) ++p;
        else p=0;
        if(p>=3) l=1;
    }
    if(l==1) cout<<"Yes";
    else cout<<"No";
    return 0;
}

Measured memory_bytes: 3672
#include <stdio.h>
#include <math.h>
int main()
{
	int A,B,C;
	scanf("%d %d %d", &A, &B, &C);
	if (A <= B) {
		if (C <= B && C >= A) {
			printf("Yes");
		}
		else {
			printf("No");
		}
	}
	else {
		if (C <= A && C >= B) { printf("Yes"); }
		else { printf("No"); }
	}
	return 0;
}


Measured memory_bytes: 128
n, W = map(int, input().split())
w = [0] * n
v = [0] * n
for i in range(n):
    w[i],v[i] = map(int, input().split())

dp = [[0] * (W + 1) for i in range(n)]
for i in range(n):
    for j in range(W+1):
        if j - w[i] < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
#print(dp)
print(dp[n-1][W])

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

int main(){
    int H,W,K; cin >> H >> W >> K;
    vector<string> S(1010);
    ll mi = 1e9;
    for(int y=0;y<H;y++) cin >> S[y];
    
    for(ll bit=0;bit<(1<<(H-1));++bit){
        vector<ll> seg(12,0);
        ll num = 0;
        for(int i=0;i<H;++i){
            seg[i] = num;
            if(bit&(1<<i)) num++;
        }
        ll res = __builtin_popcount(bit);
        vector<ll> count(12);
        for(int x=0;x<W;x++){
            for(int y=0;y<H;y++){
                if(S[y][x] == '1') count[seg[y]]++;
            }
            for(int i=0;i<num+1;i++){
                if(count[i]>K){
                    res++;
                    for(int y=0;y<num+1;++y) count[y] = 0;
                    for(int y=0;y<H;y++) if(S[y][x] == '1') count[seg[y]]++;
                    break;
                }
            }
            for(int i=0;i<num+1;i++)if(count[i]>K) res=1e9;
        }
        mi = min(mi,res);
    }
    cout << mi << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
void trace(int A[],int N){
  int i;
  for(i=0;i<N;i++){
    if(i>0) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
}

void insertionSort(int A[],int N){
  int j,i,v;
  for(i=1;i<N;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
    trace(A,N);
  }
}

int main(){
  int N,i,j;
  int A[100];

  scanf("%d",&N);
  for(i=0;i<N;i++) scanf("%d",&A[i]);

  trace(A,N);
  insertionSort(A,N);

  return 0;
}

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

int main() {
  int n;
  cin >> n;
  int m = n % 10;
  
  if(m == 3) cout << "bon";
  else if(m == 0 || m == 1 || m == 6 || m == 8) cout << "pon";
  else cout << "hon";
}



Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define pb push_back

typedef long long ll;
typedef pair<int,int> pi;
const int MAXN = (int)1e6+7;

ll val[83][83],H,W;
bool dp[83][83][160*190];

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

    cin >> H >> W;
    rep(i,1,H) {
        rep(j,1,W) {
            cin >> val[i][j];
        }
    }

    rep(i,1,H) {
        rep(j,1,W) {
            int tmp;
            cin >> tmp;
            val[i][j] = abs(val[i][j]-tmp);
        }
    }

    dp[1][1][80*160-val[1][1]] = 1;
    dp[1][1][80*160+val[1][1]] = 1;
    rep(i,1,H) {
        rep(j,1,W) {
            if (i!=H) {
                int dx = i+1,dy = j;
                rep(k,0,160*160) {
                    if (dp[i][j][k]) {
                        dp[dx][dy][k+val[dx][dy]] = 1;
                        dp[dx][dy][k-val[dx][dy]] = 1;
                    }
                }
            }
            if (j!=W) {
                int dx = i,dy = j+1;
                rep(k,0,160*160) {
                    if (dp[i][j][k]) {
                        dp[dx][dy][k+val[dx][dy]] = 1;
                        dp[dx][dy][k-val[dx][dy]] = 1;
                    }
                }
            }
        }
    }

    rep(k,0,80*160) if (dp[H][W][80*160+k]) {
        cout << k << endl;
        break;
    }
}




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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int std_in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};
const int MOD = 1000000007;


signed main(){
    int n;
    cin >> n;
    PRINT(1110 - n);
    return 0;
}

Measured memory_bytes: 384
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container, std.range;

void main()
{
    auto ps = new int[](10^^6+1);
    foreach (i; 2..10^^6+1) if (ps[i] == 0) {
        auto x = i;
        while (x <= 10^^6) {
            ps[x] = i;
            x += i;
        }
    }

    auto N = readln.chomp.to!int;
    auto ns = new int[](10^^6+1);
    foreach (a; readln.split.to!(int[])) {
        while (a != 1) {
            auto p = ps[a];
            ns[p] += 1;
            while (a % p == 0) a /= p;
        }
    }

    auto pc = true;
    foreach (p; ns) {
        if (p == N) {
            writeln("not coprime");
            return;
        } else if (p > 1) {
            pc = false;
        }
    }
    writeln(pc ? "pairwise coprime" : "setwise coprime");
}

Measured memory_bytes: 55312
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9 + 7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, R, S, T, U, V, W, x, y, z;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;
typedef long long ll;
typedef pair<ll, ll> Pa;

int main() {
	string s;
	cin >> s;
	int cnt = 0;
	rep(i, 3){
		if(s[i] == 'o') cnt++;
	}
	cout << 700+cnt*100;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
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; }
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s[k-1] += 'a'-'A';
    cout << s << endl;
}

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

int X[11][11];

int batu(int a, int b, int c, int d) {	
	int e = X[0][a];
	int f = X[e][b];
	e = X[f][c];
	f = X[e][d];
	return f;
}

bool check(int a, int b, int c, int d, int e) {
	int f = X[0][a];
	int g = X[f][b];
	f = X[g][c];
	g = X[f][d];
	return !!X[g][e];
}

int main() {
	for ( int i = 0; i < 10; i++ ) {
		for ( int j = 0; j < 10; j++ ) cin >> X[i][j];
	}

	int ans = 0;
	for ( int a = 0; a < 10; a++ ) {
		for ( int b = 0; b < 10; b++ ) {
			for ( int c = 0; c < 10; c++ ) {
				for ( int d = 0; d < 10; d++ ) {					
					int e = batu(a, b, c, d);							
					bool flag = true;
					for ( int i = 0; i < 10; i++ ) {
						if ( i == a ) continue;
						flag &= check(i, b, c, d, e);
					}

					for ( int i = 0; i < 10; i++ ) {
						if ( i == b ) continue;
						flag &= check(a, i, c, d, e);
					}

					for ( int i = 0; i < 10; i++ ) {
						if ( i == c ) continue;
						flag &= check(a, b, i, d, e);
					}

					for ( int i = 0; i < 10; i++ ) {
						if ( i == d ) continue;
						flag &= check(a, b, c, i, e);
					}

					for ( int i = 0; i < 10; i++ ) {
						if ( i == e ) continue;
						flag &= check(a, b, c, d, i);
					}
					
					if ( a != b ) flag &= check(b, a, c, d, e);
					if ( b != c ) flag &= check(a, c, b, d, e);
					if ( c != d ) flag &= check(a, b, d, c, e);
					if ( d != e ) flag &= check(a, b, c, e, d);					

					if ( !flag ) ans++;					
				}
			}
		}
	}

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



Measured memory_bytes: 3100
/*
 * Created by Dipta Das on 08-05-2019
 * Title: 
 * Problem Link: 
 * Editorial: 
 * Source Code: 
 * Comments: 
*/

#include <bits/stdc++.h>
#include <stdio.h>
#define fin freopen("input", "r", stdin)
#define whatis(x) cerr << #x << ": " << x << endl;

using namespace std;
using ll = long long;

const int inf = 1e9 + 5;

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

    int n;
    cin >> n;
    vector<int> h(n);
    for (int &i : h) cin >> i;
    vector<int> dp(n, inf);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        if (i-1 >= 0) dp[i] = min (dp[i], abs(h[i]-h[i-1]) + dp[i-1]);
        if (i-2 >= 0) dp[i] = min (dp[i], abs(h[i]-h[i-2]) + dp[i-2]);
    }

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


    return 0;
}



Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
////////////////////////////////////////////////////////////////////////
int main(){
    int n=gn();
    int ans=(n%1000)==0?0:1000-(n%1000);
    print(ans),putchar(10);
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/

Measured memory_bytes: 3592
h, w = gets.split.map(&:to_i)

ans = 10 ** 20
(1..h-1).each do |h1|
  # pattern1
  if h - h1 >= 2
    h2 = (h-h1)/2
    h3 = (h-h1)-h2
    areas = []
    areas = [h1*w, h2*w, h3*w]
    ans = [ans, areas.max-areas.min].min
  end
  # pattern2
  w2 = w/2
  w3 = w-w2
  areas = [h1*w, (h-h1)*w2, (h-h1)*w3]
  ans = [ans, areas.max-areas.min].min
end

(1..w-1).each do |w1|
  # pattern1
  if w - w1 >= 2
    w2 = (w-w1)/2
    w3 = (w-w1)-w2
    areas = []
    areas = [w1*h, w2*h, w3*h]
    ans = [ans, areas.max-areas.min].min
  end
  # pattern2
  h2 = h/2
  h3 = h-h2
  areas = [w1*h, (w-w1)*h2, (w-w1)*h3]
  ans = [ans, areas.max-areas.min].min
end

puts ans

Measured memory_bytes: 1788
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;
const int mod = 7*17*(1<<23) + 1;
const ll inf = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
short dp[330][330][330];
int n, k;
string s, t;
short f(int i, int j, int k) {
	if(k<0) return -3;
	if(i>j) return 0;
	if(i==j) return 1;
	if(dp[i][j][k] != -1) return dp[i][j][k];
	dp[i][j][k] = max(f(i+1,j,k), f(i,j-1,k));
	dp[i][j][k] = max(dp[i][j][k], (short)(f(i+1,j-1,k - (s[i]!=s[j])) + 2));
//	cout << i << " " << j << " " << k << " " << dp[i][j][k] << "\n";
	return dp[i][j][k];
//			dp[i][j][k] = max(dp[]);
}
int main() { //DINIC ORZ, FFT ORZ
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s >> k;
	memset(dp, -1, sizeof dp);
	cout << f(0, s.size()-1, k);
}


Measured memory_bytes: 70528
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#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(){
    bool s[1000005] = {0}, f;
    s[1] = true;
    s[0] = false;
    int i = 1;
    rep(i, 1000005){
        if(s[i] == true){
            if(i * 2 < 1000005){
                s[i * 2] = true;
            }
            if(i * 3 < 1000005){
                s[i * 3] = true;
            }
            if(i * 5 < 1000005){
                s[i * 5] = true;
            }
        }
    }
    int m,n;
    while(cin >> m, m){
        cin >> n;
        int ans = 0;
        range(j, m, n + 1){
            if(s[j] == true)
                ans++;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 2144
#ABC131-E Friendships
"""
問題：
頂点数n,辺数mとして最短距離が2となる辺がk個となる
重みなし無向グラフが存在するかを調べる。
解法：
まず、うにグラフの状態がkの最大値であることが言える。
(うにグラフ…頂点1に全ての頂点を繋いだ状態。n-1辺になる。)
この時のkは2頂点の組み合わせ数(n-1)C2なので、これを超えるkは
満たせず、そうでなければ適当な2頂点を繋げばそれ以下の値を全て
満たせることになる。(二頂点を繋いでも他の辺の最短距離に影響しない)
"""
import sys
import itertools
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k = map(int,readline().split())

#二項係数(modなし) O(k)
def large_conbination(n,k): #no mod. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
    res2 = 1
    for i in range(1,k+1):
        res2*= i
    return res1//res2

mx = large_conbination(n-1,2) #うにグラフ状態

if k > mx:
    print(-1)
else:
    graph = []
    for i in range(1,n):
        graph.append((1,i+1)) #うにグラフの作成
    count = 0
    for i in itertools.combinations([i for i in range(2,n+1)],2):
        if k == mx-count:
            break
        graph.append(i)
        count += 1
    print(len(graph))
    for i,j in graph:
        print(i,j)

Measured memory_bytes: 43120
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

map<ll, ll> prime_factor(ll n){
    map<ll,ll> com;
    for(ll i = 2LL; i*i<=n; ++i){
        while(n%i==0LL){
            com[i]++;
            n /= i;
        }
    }
    if(n != 1LL)com[n]++;
    return com;
}


int main(){
	int N; 
	cin >> N;
	map<ll, ll> facts;
	REP(i,N){
		map<ll, ll> t = prime_factor(i);
		for(auto x:t){
			facts[x.first] += x.second;
		}
	}
	int ans = 0;
	//74
	for(auto x:facts){
		if(x.second >= 74) ++ans;
	}
	//2 * 24
	for(auto x:facts){
		for(auto y:facts){
			if(!(x.first < y.first))continue;
			if(x.second >= 2 && y.second >= 24) ++ans;
			if(x.second >= 24 && y.second >= 2) ++ans;
		}
	}
	//4*14
	for(auto x:facts){
		for(auto y:facts){
			if(!(x.first < y.first))continue;
			if(x.second >= 4 && y.second >= 14) ++ans;
			if(x.second >= 14 && y.second >= 4) ++ans;
		}
	}
	//2 * 4 * 4
	for(auto x: facts){
		for(auto y:facts){
			for(auto z: facts){
				if(!(x.first < y.first && y.first < z.first))continue;
				int a = (x.second >= 2) + (y.second >= 2) + (z.second >= 2);
				int b = (x.second >= 4) + (y.second >= 4) + (z.second >= 4);
				if(a >= 3 && b >= 3) ans += 3;
				else if(a >= 3 && b >= 2) ++ans;
			}
		}
	}
	//for(auto x: facts){
	//	printf("[%lld]->%lld.\n", x.first, x.second);
	//}
	cout << ans << endl;
	return 0;
}


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

int main()
{
    int n = 5;
    vector<int> x(n);
    rep(i,n)cin >> x[i];

    rep(i,n){
        if (x[i] == 0){
            cout << i + 1 << endl;
            return 0 ;
        }
    }


    return 0;
}


Measured memory_bytes: 3632
/*  -*- coding: utf-8 -*-
 *
 * c.cc: C: GCD on Blackboard
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

/* global variables */

int gcd(int m, int n) {
  if (m < n) swap(m, n);
  while (n > 0) {
    int r = m % n;
    m = n;
    n = r;
  }
  return m;
}

/* subroutines */

int as[MAX_N], gascs[MAX_N], gdscs[MAX_N];

/* main */

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++) scanf("%d", as + i);

  gascs[0] = as[0];
  for (int i = 1; i < n; i++)
    gascs[i] = gcd(gascs[i - 1], as[i]);

  gdscs[n - 1] = as[n - 1];
  for (int i = n - 2; i >= 0; i--)
    gdscs[i] = gcd(gdscs[i + 1], as[i]);

  int maxg = 0;
  for (int i = 0; i < n; i++) {
    int g;
    if (i == 0) g = gdscs[1];
    else if (i == n - 1) g = gascs[n - 2];
    else g = gcd(gascs[i - 1], gdscs[i + 1]);
    if (maxg < g) maxg = g;
  }

  printf("%d\n", maxg);
  return 0;
}


Measured memory_bytes: 1408
import sys
N=int(input())
a=[[] for i in range(N)]
for i in range(N):
    a[i]=input()
    
for i in range(N):
    if i>0:
        if a[i-1][len(a[i-1])-1]!=a[i][0]:
            print("No")
            sys.exit()

for i in range(N):
    for j in range(1,N-i-1):
        if a[i] == a[N-j]:
                print("No")
                sys.exit()

print("Yes")


Measured memory_bytes: 3064
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

    dp = [[0] * (W+1) for _ in range(N+1)] 

    for i in range(N):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j - w] + v)
 
    print(dp[N][W])
 
if __name__ == "__main__":
    resolve()

Measured memory_bytes: 118512
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
long long Read() {
    long long x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
int main() {
    int a,b;
    char str;
    cin>>a>>str>>b;
    if(str=='-') cout<<a-b<<endl;
    if(str=='+') cout<<a+b<<endl;
	return 0;
}

Measured memory_bytes: 256