akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using u32 = uint32_t;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define MAXC(c, x) (c = max(c, x))
#define MINC(c, x) (c = min(c, x))

#define REP(i,n) for(auto i = 0 * (n), i##_len = (n); i < i##_len; ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,n) for(ll i=s, i##_len=(ll)(n); i<i##_len; ++i)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

const ll INF = 1e9;

template<typename F> double bsearch(double ok, double ng, ll loop, F f) {
	REP(i, loop) {
		double middle = (ok + ng) / 2;
		(f(middle) ? ok : ng) = middle;
	}
	return ok;
}


int main() {
	#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
	#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);
	ll h, w, k; cin >> h >> w >> k;
	vvb maze(h, vb(w, false));
	ll sx, sy;
	REP(i, h) REP(j, w) {
		char c;  cin >> c;
		if (c == '#') maze[i][j] = true;
		if (c == 'S') {
			sx = j; sy = i;
		}
	}
	vvl dict(h, vl(w, TEN(10)));
	vl dx = { 0, 1, 0, -1 };
	vl dy = { 1, 0, -1, 0 };
	using P = tuple<ll, ll, ll>;
	deque<P> q;
	q.push_back(P{ sx, sy, 0 });
	ll mi = TEN(10);
	while (!q.empty()) {
		auto p = q.front(); q.pop_front();
		ll x = get<0>(p); ll y = get<1>(p);
		ll d = get<2>(p);
		if (dict[y][x] < d) continue;
		mi = min(mi, x);
		mi = min(mi, w - x - 1);
		mi = min(mi, y);
		mi = min(mi, h - y - 1);
		if (d == k) continue;
		REP(i, 4) {
			ll nx = dx[i] + x;
			ll ny = dy[i] + y;
			if (!maze[ny][nx]) {
				if (nx == 0 || ny == 0 || nx == w - 1 || ny == h - 1) {
					cout << 1 << endl;
					return 0;
				}
				if (dict[ny][nx] > d + 1) {
					dict[ny][nx] = d + 1;
					q.push_back(P{ nx, ny, d + 1 });
				}
			}
		}
	}
	cout << mi / k + (mi % k != 0) + 1 << endl;
	return 0;
}


Measured memory_bytes: 5376
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
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, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().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): pass
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 = 10 ** 9 + 7

n = I()

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod

s = input()
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1
for i in range(1, n):
    ret = 0
    if s[i - 1] == "<":
        for j in range(i - 1, -1, -1):
            ret += dp[i - 1][j]
            ret %= mod
            dp[i][j] = ret
    else:
        for j in range(1, i + 1):
            ret += dp[i - 1][j - 1]
            dp[i][j] = ret
        dp[i][i] = ret

print(sum(dp[-1]) % mod)


Measured memory_bytes: 573196
a,b,c = map(int,input().split())
k = int(input())
x = 0
while 1:
    if b > a:
        break
    else:
        b *= 2
        x += 1
y = 0
while 1:
    if c > b:
        break
    else:
        c *= 2
        y += 1
if x + y <= k:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9128
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(obj) (obj).begin(),(obj).end()
typedef long long llong;
llong mod=1e9+7;

int w,h,cnt;
int a[50][50];
void dfs(int i,int j){
  if(a[i][j]==0) return;
  if(i<0||i>=w||j<0||j>=h) return;
  a[i][j]=0;
  dfs(i-1,j-1);
  dfs(i-1,j);
  dfs(i-1,j+1);
  dfs(i,j-1);
  dfs(i,j+1);
  dfs(i+1,j-1);
  dfs(i+1,j);
  dfs(i+1,j+1);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(1){
    cnt=0;
    cin>>h;
    if(h=='\0') break;
    cin>>w;
    rep(i,w){
      rep(j,h){
        cin>>a[i][j];
      }
    }
    rep(i,w){
      rep(j,h){
        if(a[i][j]==1){
          dfs(i,j);
          cnt++;
        }
      }
    }
    cout<<cnt<<endl;
  }

  return 0;
  }



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

int main()
{
  int A, B, C;
  cin >> A >> B >> C;

  if (A == B && A != C) {
    cout << "Yes" << endl;
    return 0;
  }
  if (B == C && A != B) {
    cout << "Yes" << endl;
    return 0;
  }
  if (A == C && A != B) {
    cout << "Yes" << endl;
    return 0;
  }

    cout << "No" << endl;
}


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


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,h;cin>>n>>h;
    ll Ma = 0;
    vector<ll> b(n);
    rep(i,n){
        ll a,bb;cin>>a>>bb;
        Ma=max(Ma,a);
        b[i]=bb;
    }
    sort(b.rbegin(),b.rend());
    ll ans = 0,idx = 0;
    while(h>0&&idx<n&&b[idx]>Ma){
        h-=b[idx];
        ans++;
        idx++;
    }
    if(h>0)ans+=(h+Ma-1)/Ma;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
using namespace std;

int n, l;
int c[100][100];
const int INF = 10001000;

void wf(int x, int y){
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++){
			c[i][j] = min(c[i][j], c[i][x] + c[x][y] + c[y][j]);
			c[i][j] = min(c[i][j], c[i][y] + c[y][x] + c[x][j]);
		}
}

int main(){
	while(1){
		scanf("%d %d", &n, &l);
		if(n == 0 && l == 0) break;
		for(int i=0; i<100; i++)
			for(int j=0; j<100; j++)
				c[i][j] = INF;
		for(int i=0; i<n; i++)
			c[i][i] = 0;
		for(int h=0; h<l; h++){
			int t;
			scanf("%d", &t);
			if(t == 0){
				int a, b;
				scanf("%d %d", &a, &b);
				if(c[a-1][b-1] == INF) printf("-1\n");
				else printf("%d\n", c[a-1][b-1]);
			}else{
				int x, y, z;
				scanf("%d %d %d", &x, &y, &z);
				c[x-1][y-1] = min(c[x-1][y-1], z);
				c[y-1][x-1] = c[x-1][y-1];
				wf(x-1, y-1);
			}
		}
	}
	return 0;
}

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

#define INF 1 << 29
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)

using namespace std;

typedef pair<int,int> pii;
typedef long long int ll;

void gen_sosuu(int sosuu[]){
  REP(i,100010){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(100000)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<=100000;j++){
      //printf("%d %d %d\n",i*j,i,j);
      sosuu[i*j] =false;
    }
  }
}

int n,m;
int a[51],b[51],c[51],d[51];

int main(){
  scanf("%d %d",&n,&m);
  REP(i,n){
    scanf("%d %d",&a[i],&b[i]);

  }
  REP(i,m){
    scanf("%d %d",&c[i],&d[i]);
  }

  REP(i,n){
    int mi = -1;
    int mi_i = 0;
    REP(j,m){
      if(mi == -1 || mi > abs(a[i]-c[j]) + abs(b[i]-d[j])){
        mi_i = j;
        mi = abs(a[i]-c[j])+abs(b[i]-d[j]);
      }
    }
    printf("%d\n",mi_i+1);
  }
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) {
		TreeMap<Integer,Integer> treeMap = new TreeMap<Integer,Integer>();
		Scanner scan = new Scanner(System.in);
		int win = 0;
		while(scan.hasNext()) {
			int num = scan.nextInt();
			for(int i = 1;i < num + 1;i++) {
				int member = scan.nextInt();
				int fish = scan.nextInt();
				treeMap.put(member,fish);
				if(win < fish) {
					win = fish;
				}
			}
			break;
		}
		for(Integer fin : treeMap.keySet()) {
			if(treeMap.get(fin) == win) {
				System.out.println(fin + " " + treeMap.get(fin));
				break;
			}
		}
		scan.close();
	}
}



Measured memory_bytes: 26276
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int P, Q, R, cost;
  cin >> P >> Q >> R;
  if(P >= Q && P >= R){
    cost = Q + R;
  } else if(Q >= P && Q >= R){
    cost = P + R;
  } else {
    cost = P + Q;
  }
  
  cout << cost << endl;
  
  return 0;
}

Measured memory_bytes: 256
use std::cmp;
use std::collections::HashMap;
use std::collections::VecDeque;
use std::io::Read;
use std::usize::MAX;

macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}
macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}
macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()}};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}

fn solve() {
    input! {
        k: usize
    }

    let mut ans = 0;
    let v = vec![
        1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4,
        1, 51,
    ];
    println!("{}", v[k - 1]);
}

fn main() {
    let thd = std::thread::Builder::new().stack_size(104_857_600);
    thd.spawn(|| solve()).unwrap().join().unwrap();

    /*
    // 入力を一括で読み込む場合
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut input = buf.split_whitespace();

    // inputに対しnext()で読み込んでいく
    let q: usize = input.next().unwrap().parse().unwrap();
    */
}

const LARGE_PRIME: u64 = 1_000_000_007;

// @〜でsnippet


Measured memory_bytes: 8572
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);

		int n=sc.nextInt();
		int[] d=new int[n];
		for(int i=0;i<n;i++) {
			d[i]=sc.nextInt();
		}
		System.out.println(Takoyaki(d));

	}

	private static int Takoyaki(int[] d) {
		int r=0;

		r=(Sum(d)*Sum(d)-Sum(SquareEach(d)))/2;
		return r;
	}

	private static int[] SquareEach(int[] d) {
		int[] r=new int[d.length];
		for(int i=0;i<d.length;i++) {
			r[i]=d[i]*d[i];
		}
		return r;
	}

	private static int Sum(int[] d) {
		int r=0;
		for(int i=0;i<d.length;i++) {
			r=r+d[i];
		}
		return r;
	}

}

Measured memory_bytes: 21972
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(void){

  string s;
  cin>>s;

  
  ll n=s.size();

  vector<ll> cnt_0(n,0);
  vector<ll> cnt_1(n,0);  

  rep(i,n){

    if(i==0){
      if(s[i] == '0') cnt_0[0]=1;
      else cnt_1[0]=1;
      continue;
    }
    if(s[i] == '0'){
      cnt_0[i] = cnt_0[i-1]+1;
      cnt_1[i] = cnt_1[i-1];
    }
    else{
      cnt_0[i] = cnt_0[i-1];
      cnt_1[i] = cnt_1[i-1]+1;
    }


  }

  cout << min(cnt_0[n-1],cnt_1[n-1])*2 << endl;

  return 0;
}



Measured memory_bytes: 2556
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using ll = long long int;

int main(){
    int A, B;
    cin >> A >> B;
    if(A*500 >= B){
        cout << "Yes";
    }
    else{
        cout << "No";
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <numeric>
using namespace std;
using ll = long long;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    cin >> N >> M;
    vec<ll> A(N+1);
    for(int i=2;i<=N;i++){
        cin >> A[i];
        A[i] += A[i-1];
    }
    vvec<ll> B(M+1,vec<ll>(N+1,0));
    for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) cin >> B[j][i];
    vvec<ll> S(N+2,vec<ll>(N+2,0));
    
    auto imos = [&](vec<ll>& b){
        set<int> s;
        s.insert(0);
        s.insert(N+1);
        vec<int> id(N);
        iota(id.begin(),id.end(),1);
        sort(id.begin(),id.end(),[&](int i,int j){return b[i]>b[j];});
        for(auto i:id){
            set<int>::iterator itl = s.upper_bound(i);
            int r = *itl;
            itl--;
            int l = *itl;
            r--; l++;
            S[l][i] += b[i];
            S[l][r+1] -= b[i];
            S[i+1][i] -= b[i];
            S[i+1][r+1] += b[i];
            s.insert(i);     
        }
    };
    
    for(int j=1;j<=M;j++) imos(B[j]);

    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) S[i][j] += S[i-1][j];
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) S[i][j] += S[i][j-1];

//    cerr << endl;
//    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) cerr << S[i][j] << (j!=N? " ":"\n");
    ll ans = 0;
    for(int i=1;i<=N;i++) for(int j=i;j<=N;j++) ans = max(ans,S[i][j]-A[j]+A[i]);
    cout << ans << endl;
}

Measured memory_bytes: 204032
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define KOZYUN(a) sort(all(a),greater<int>())
#define int ll
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
#define IN(a) cin >> a
#define INT(a) int a; cin >> a
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    char x,y; cin >> x >> y;
    if(x < y) OUT('<');
    else if(x == y) OUT('=');
    else OUT('>');

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
int cmp(const void *a, const void *b);
//your code here!

int main(void){
    char s[15], t[15], r[15];
    scanf("%s %s %s", s, t, r);
    printf("%c%c%c\n", s[0]-32, t[0]-32, r[0]-32);
    return 0;
}

int cmp(const void *a, const void *b){
    ll A=*(ll *)a, B=*(ll *)b;
    if(A==B)return 0;
    else return A>B ? 1:-1;//昇順ソート
}


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


int main() {long W, H, N;
cin >> W >> H >> N;
vector<long> x(N + 1); vector<long> y(N + 1); vector<long> a(N + 1);
erep(i, N) cin >> x.at(i) >> y.at(i) >> a.at(i);
long xmin = 0; long xmax = W; long ymin = 0; long ymax = H;
erep(i, N){
  if(a.at(i) == 1) xmin = max(xmin, x.at(i));
  else if(a.at(i) == 2) xmax = min(xmax, x.at(i));
  else if(a.at(i) == 3) ymin = max(ymin, y.at(i));
  else if(a.at(i) == 4) ymax = min(ymax, y.at(i));
}
long zero = 0;
long ans = max(zero, xmax - xmin) * max(zero, ymax - ymin);







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



Measured memory_bytes: 256
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define rep1n(i, n) for(int i=1;i<=(int)(n);i++)
#define all(t) t.begin(), t.end()
#define rall(t) t.rbegin(), t.rend()
#define mat(type, row, col, init) vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout<<(cond? "Yes":"No")<<endl;
#define YES(cond) cout<<(cond? "YES":"NO")<<endl;

int main() {
	int n;
	cin >> n;
	vector<ll>a(n);
	rep(i, n)cin >> a[i];
	auto f = [&](int one) {
		ll s = 0;
		ll cnt = 0;
		rep(i, n) {
			s = s + a[i];
			if (i % 2 == one) {
				if (s <= 0) {
					cnt += -s + 1;
					s = 1;
				}
			}
			else {
				if (s >= 0) {
					cnt += s + 1;
					s = -1;
				}
			}
		}
		return cnt;
	};
	cout << std::min(f(0), f(1));

	return 0;
}





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

long long N, K;
vector<long long> xvec;
vector<long long> yvec;
long long x[100];
long long y[100];

long long count(long long x1, long long x2, long long y1, long long y2){
	long long ret = 0;

	for(long long i = 0; i < N; i++){
		if(x1 <= x[i] && x[i] <= x2 && y1 <= y[i] && y[i] <= y2)
			ret++;
	}
	return ret;
}

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

	long long ans = LONG_MAX;
	for(long long i = 0; i < N; i++){
		for(long long j = i+1; j < N; j++){
			for(long long k = 0; k < N; k++){
				for(long long l = k+1; l < N; l++){
					long long x1,x2,y1,y2;
					x1 = min(x[i], x[j]);
					x2 = max(x[i], x[j]);
					y1 = min(y[k], y[l]);
					y2 = max(y[k], y[l]);

					if(count(x1, x2, y1, y2) >= K){
						ans = min(ans, (x2 - x1) * (y2 - y1));
					}
				}
			}
		}
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
#include <cstdio>
//#include <iostream>
//#include <string>

using namespace std;

// cl /EHsc xxx.cpp
int main(int argc, char *argv[])
{
	int n;
	scanf("%d", &n);
	
	int *ary = new int[n];
	
	int v;
	int t = n;
	while (t)
	{
		scanf("%d", &v);
		ary[--t] = v;
	}
	
	for (int j = 0; j < n; j++)
	{
		printf((j == n-1) ? "%d\n" : "%d ", ary[j]);
	}
	
	delete[] ary;
	
	return 0;
}

Measured memory_bytes: 1028
n, w = map(int, input().split())
goods = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if 0 <= j - goods[i][0]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - goods[i][0]] + goods[i][1])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(dp[n][w])


Measured memory_bytes: 121068
#include<bits/stdc++.h>
#include<iomanip>
#include<numeric>

using namespace std;
using ll = long long;
constexpr int mo = 1e9+7;
constexpr int  mod = mo;
constexpr int inf = 1<<30;
int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    int count = 0;
    if(a ==b and b==c ){
        if(a%2)cout << 0 << endl;
        else cout << -1 << endl;
        return 0;
    }
    while(true){
        ll ab,ac,bc;
        ab = a+b;
        ac = a+c;
        bc = b+c;
        if(ab%2 or ac%2 or bc%2){
            cout << count << endl;
            break;
        }
        a = bc/2;
        b = ac/2;
        c = ab/2;
        count++;
    }
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define nmax_def 110000
#define Cmax_def 2200
#define mod 998244353
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

vl pow_;
vector<vl> pow_23;
void pow_ini(ll n) {
	pow_.push_back(n);
	rep(j, 62) {
		ll nxt = pow_[j] * pow_[j];
		nxt %= mod;
		pow_.push_back(nxt);
	}
	for (ll i = 2; i <= 3; i++) {
		vl powtmp;
		powtmp.push_back(i);
		rep(j, 62) {
			ll nxt = powtmp[j] * powtmp[j];
			nxt %= mod;
			powtmp.push_back(nxt);
		}
		pow_23.push_back(powtmp);
	}
	return;
}

ll pow1(ll k) {
	ll ans = 1;
	rep(ntmp, 62) {
		if ((k >> ntmp) % 2 == 1) {
			ans *= pow_[ntmp];
			ans %= mod;
		}
	}
	return ans;
}

ll pow1_23(ll i, ll k) {
	ll ans = 1;
	rep(ntmp, 62) {
		if ((k >> ntmp) % 2 == 1) {
			ans *= pow_23[i - 2][ntmp];
			ans %= mod;
		}
	}
	return ans;
}

vl fact;
vl fact_inv;

void fact_ini(ll n) {
	fact.push_back(1);
	fact.push_back(1);
	for (ll i = 2; i <= n; i++) {
		ll fact_tmp = fact[i - 1] * i;
		fact_tmp %= mod;
		fact.push_back(fact_tmp);
	}
	fact_inv.resize(n + 1);
	pow_ini(fact[n]);
	fact_inv[n] = pow1(mod - 2);
	for (ll i = n - 1; i >= 0; i--) {
		fact_inv[i] = fact_inv[i + 1] * (i + 1);
		fact_inv[i] %= mod;
	}
}

ll nCm(ll n, ll m) {
	ll ans = fact[n] * fact_inv[m];
	ans %= mod;
	ans *= fact_inv[n - m];
	ans %= mod;
	return ans;
}

int main() {
	fact_ini(2 * pow(10, 7));
	ll N;
	cin >> N;
	ll ans1 = pow1_23(3, N);
	ll ans2 = 0;
	ll M = N / 2 + 1;
	for (ll i = M; i <= N; i++) {
		ll anstmp = nCm(N, i);
		anstmp *= pow1_23(2, N - i);
		anstmp %= mod;
		ans2 += anstmp;
	}
	ans2 *= 2;
	ans2 %= mod;
	ll ans = ans1 - ans2 + mod;
	ans %= mod;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 314836
#include <bits/stdc++.h>
#define pii pair<int,int> 
#define fi first
#define pb push_back
#define si second
#define int   long long 
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mod 1000000007
#define all(o) o.begin(),o.end()
using namespace std;
int32_t main(){	
	string s;
	int k;
	cin>>k>>s;
	int n=s.length();
	if(n<=k)
		cout<<s;
	else 
	{
		cout<<s.substr(0,k)+"...";
	}
	
	
}


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

using namespace std;

using ll = long long;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
    cin.tie(0);
    cout << fixed << setprecision(10);

    string l; cin >> l;
    int n = l.size();
    vector<ll> po3(n+1), po2(n+1);
    ll tmp2 = 1, tmp3 = 1;
    for(int i=0;i<=n;++i) {
      po2[i] = tmp2;
      po3[i] = tmp3;
      tmp2 *= 2;
      tmp2 %= MOD;
      tmp3 *= 3;
      tmp3 %= MOD;
    }
    ll su = 0;
    int e = 0;;
    for(int i=0;i<n;++i) {
      if(l[i] == '1') {
        su += po2[e] * po3[(int)(l.size())-i-1] % MOD;
        su %= MOD;
        e++;
      }
    }
    su += po2[e];
    su %= MOD;
    cout << su << endl;
    // printv(dp);
    
}

Measured memory_bytes: 2048
#include <iostream>
#include <stdio.h>

using namespace std;

typedef long long ll;

int main(){
    ll A,B,C,K;
    cin>>A>>B>>C>>K;
    
    if(A>=K){
        cout<<K<<endl;
    }else if(A+B>=K){
        cout<<A<<endl;
    }else if(A+B+C>=K){
        cout<<A-(K-(A+B))<<endl;
    }
    
    
    
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
 
typedef long long   ll;
typedef long double ld;
const int N  = 5e5+10;
const ll mod = 1e9+7;
const ll inf = 1e18;
 
#define fast            ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb              push_back
#define mp              make_pair
#define ub              upper_bound                 // first element >  val(itr)
#define lb              lower_bound                 // first element >= val(itr) 
#define all(x)          (x).begin(),(x).end()
#define reset(a,x)      memset(a,x,sizeof(a))       // x can be 0 or -1
#define leadzero(a)     __builtin_clz(a)            // count leading zeroes
#define trailzero(a)    __builtin_ctz(a)            // count trailing zeroes
#define bitcount(a)     __builtin_popcount(a)       // count set bits
#define iceil(n,x)      ((n)+(x)-1)/(x)
#define test            int t; cin>>t; while(t--)
#define forn(i,a,e)     for(ll i = a; i < e; i++)
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define sp              <<" "<<
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << endl;
  err(++it, args...);
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;    }
ll powm(ll base,ll exp){ll ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
ll add(ll a,ll b)  { return (a%mod+b%mod)%mod;        }
ll sub(ll a, ll b) { return (a%mod+mod-b%mod)%mod;    }
ll mult(ll a,ll b) { return ((a%mod)*(b%mod))%mod;    }
ll choose2(ll n)   { ll ans=(n*(n-1))/2; return ans;  }
ll dist2(ll x1,ll y1,ll x2,ll y2){ ll ans=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1); return ans;}

int main()
{
    fast
    ll n,x;
    cin>>n>>x;

    ll L[n];
    forn(i,0,n)
    cin>>L[i];
    
    ll d=0;
    ll cnt=1;
    forn(i,0,n)
    {
      d+=(L[i]);
      if(d<=x)
        cnt++;
      else
        break;
    }

    cout<<cnt;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>

using namespace std;

const double EPS = 1e-8;

int dcmp(double d) {
    if (fabs(d) < EPS) {
        return 0;
    }
    else {
        return d < 0? -1 : 1;
    }
}

struct Vector {
    double x, y;
    Vector(double x = 0, double  y = 0):x(x), y(y) {
    }
};

typedef Vector Point;

Vector operator-(const Vector& a, const Vector& b) {
    return Vector(a.x - b.x, a.y - b.y);
}

double cross(const Vector& a, const Vector& b) {
    return a.x * b.y - a.y * b.x;
}

double ccw(const Point& a, const Point& b, const Point& c) {
    return cross(b - a, c - a);
}

int main() {
    int n; 
    cin >> n;
    vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    
    bool isConvex = true;
    for (int i = 0; i < n - 1; i++) {
        double area = ccw(p[i], p[(i + 1) % n], p[(i+ 2) % n]);
        if (dcmp(area) < 0) {
            isConvex = false;
            break;
        }
    }
    
    cout << (isConvex? 1 : 0) << endl;
    
    return 0;
}

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

#include <map>
int main(){
    map<string,int> ans;
    int n; cin >> n;
    while(n--){
        string str;cin >> str;
        ans[str]++;
    }
    string res[] = {"AC","WA","TLE","RE"};
    for(auto &a:res){
        printf("%s x %d\n",a.c_str(),ans[a]);
    }
}

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

int main(void)
{
	map<int,int>mp;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		mp[x]++;
	}
	int sum=0;
	map<int,int>::iterator t;
	for(t=mp.begin();t!=mp.end();t++)
	{
		if((*t).second>=(*t).first)
			sum+=(*t).second-(*t).first;
		else
			sum+=(*t).second;
	}
	printf("%d\n",sum);

	return 0;
}

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

using namespace std;
typedef long long ll;
#define int ll

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

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
const int MAX_N = 100010;

vector<int> GetDivisor(int n) {
    vector<int> v;
    for(int i = 1; i*i <= n; ++i) {
        if(n % i == 0) {
            v.push_back(i);
            if(i != n / i) { v.push_back(n / i); }
        }
    }
    sort(v.begin(), v.end());
    return v;
}

template< typename T >
class CumulativeSum
{
public:
    CumulativeSum() {}
    CumulativeSum(int sz) : m_Data(sz, T(0)) {};

    void Init(int sz) { m_Data.assign(sz, T(0)); }

    // k に x を加える O(1)
    void Add(int k, T x) {
        assert(static_cast<int>(m_Data.size()) >= k);
        if(static_cast<int>(m_Data.size()) <= k) { m_Data.push_back(x); }
        else { m_Data[k] = (m_Data[k] + x); }
    }

    // 累積和の構築 O(m_Data.size())
    void Build() {
        for(int i = 1; i < static_cast<int>(m_Data.size()); i++) {
            m_Data[i] = (m_Data[i] + m_Data[i - 1]);
        }
    }

    // 区間 [0, k] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int k) {
        if(k < 0) { return T(0); }
        return (m_Data[min(k, static_cast<int>(m_Data.size()) - 1)]);
    }

    // 区間 [l, h] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int l, int h) {
        return (this->Query(h) - this->Query(l-1));
    }
private:
    vector< T > m_Data;
};

int N, K;
vector<int> A;

// n を約数とする最小の変化量
int Check(int n) {
    // cs の作成
    vector< pair<int, int> > A_pn;
    CumulativeSum<int> cs_p(N), cs_n(N);
    REP(i, N) {
        int p_val = n - (A[i] % n);
        int n_val = A[i] % n;
        A_pn.push_back(make_pair(p_val, n_val));
    }
    SORT(A_pn);
    REP(i, N) {
        cs_p.Add(i, A_pn[i].first);
        cs_n.Add(i, A_pn[i].second);
    }
    cs_p.Build();
    cs_n.Build();

    // 累積和が等しくなる場所を探す
    REP(i, N-1) {
        if(cs_p.Query(0, i) == cs_n.Query(i + 1, N-1)) {
            return cs_p.Query(0, i);
        }
    }
    return -1;
}

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

    cin >> N >> K;
    A.resize(N);

    int a_sum = 0;
    REP(i, N) {
        cin >> A[i];
        a_sum += A[i];
    }

    auto a_div = GetDivisor(a_sum);
    //a_div.push_back(a_sum);

    int ans = 1;
    for(auto cand : a_div) {
        //if(cand > a_sum / N) { break; }
        auto res = Check(cand);
        if(res > 0 && res <= K) {
            chmax(ans, cand);
        }
    }

    printf("%lld\n", ans);

    return 0;
}


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

int main(){
	int n; cin>>n;
	ll L0=2;	ll L1=1;
	ll Ln;
	if(n==1) {cout<<1<<endl; return 0;}
	rep(i,n-1){
		Ln=L1+L0;
		L0=L1;
		L1=Ln;
	}
	cout<<Ln<<endl;
}

Measured memory_bytes: 3580
N = int(input())
S = input()
    
total = []
_sum1 = []
_sum2 = []
if S[0] == "W":
    _sum1.append(1)
else:
    _sum1.append(0)
if S[-1] == "E":
    _sum2.append(1)
else:
    _sum2.append(0)

for i in range(1,N):
    if S[i] == "W":
        _sum1.append(_sum1[i-1]+1)
    else:
        _sum1.append(_sum1[i-1])
    if S[-(i+1)] == "E":
        _sum2.append(_sum2[i-1]+1)
    else:
        _sum2.append(_sum2[i-1])

j = 0
for k in _sum2[::-1]:
    total.append(_sum1[j] + k)
    j += 1

print(min(total)-1)

Measured memory_bytes: 32080
N, C = map(int, input().split())
X, V = [], []
for i in range(N):
    x, v = map(int, input().split())
    X.append(x)
    V.append(v)

st1 = [0] * N
st2 = [0] * N
st1[0] = max(0, V[0] - X[0])
st2[0] = max(0, V[0] - 2 * X[0])
cur1, cur2 = V[0] - X[0], V[0] - 2 * X[0]
pre = X[0]
for i in range(1, N):
    cur1 += V[i] - (X[i] - pre)
    cur2 += V[i] - (X[i] - pre) * 2
    st1[i] = max(st1[i - 1], cur1)
    st2[i] = max(st2[i - 1], cur2)
    pre = X[i]

ba1 = [0] * N
ba2 = [0] * N
ba1[-1] = max(0, V[-1] - (C - X[-1]))
ba2[-1] = max(0, V[-1] - 2 * (C - X[-1]))
cur1, cur2 = V[-1] - (C - X[-1]), V[-1] - 2 * (C - X[-1])
pre = X[-1]
for i in range(N - 2, -1, -1):
    cur1 += V[i] - (pre - X[i])
    cur2 += V[i] - (pre - X[i]) * 2
    ba1[i] = max(ba1[i + 1], cur1)
    ba2[i] = max(ba2[i + 1], cur2)
    pre = X[i]

num = 0
num = max(st1[N - 1], ba1[0])
for i in range(N - 1):
    num = max(num, st1[i] + ba2[i + 1])

for i in range(1, N - 1):
    num = max(num, ba1[i] + st2[i - 1])

print(num)

Measured memory_bytes: 25952
n,m=map(int,input().split())
ab=[]
for i in range(m):
    ab.append(list(map(int,input().split())))
l=[]
for i in range(n):
    l.append(0)

for i in range(m):
         l[ab[i][0]-1]+=1
         l[ab[i][1]-1]+=1
for i in range(n):
         print(l[i])

Measured memory_bytes: 3064
n, a, b = map(int, input().split())
 
mod = 10 ** 9 + 7
 
if n == 2:
   print(0)
   exit()
                
S = pow(2, n, mod) -1 

x1 = 1
y1 = 1
for i in range(a):
  x1 = x1 * (n-i) % mod
  y1 = y1 * (i+1) % mod
A = (x1 * pow(y1, mod - 2, mod)) % mod

x2 = 1
y2 = 1
for i in range(b):
  x2 = x2 * (n-i) % mod
  y2 = y2 * (i+1) % mod
B = (x2 * pow(y2, mod - 2, mod)) % mod

print((S - A - B) % mod)

Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007


int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt[26] = {};
	for(int i = 0; i < s.length(); i++){
		cnt[s[i] - 'a']++;
	}
	long long int ans = 1;
	for(int i = 0; i < 26; i++){
		ans = (ans * (cnt[i] + 1)) % mod;
	}
	ans = (ans - 1 + mod) % mod;
	cout << ans << endl;
}

Measured memory_bytes: 512
package main

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

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	k := nextInt()
	as := make([]int, n)
	for i := 0; i < n; i++ {
		as[i] = nextInt()
	}

	sum := 0
	for i := 0; i < n; i++ {
		sum += as[i]
		if k <= i {
			if as[i-k] < as[i] {
				fmt.Println("Yes")
			} else {
				fmt.Println("No")
			}
			sum -= as[i-(k-1)]
		}
	}
}

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}


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

using ll = long long;
using namespace std;

const ll mod = 1e9 + 7;
const ll MAX = 1e6;

ll fac[MAX];

void init(){
    fac[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
}

ll rep_pow(int n, int p) { // n^p
    if (p == 0) {
        return 1;
    }
    if (p % 2 == 0) {
        ll t = rep_pow(n, p / 2);
        return t * t % mod;
    } else {
        return n * rep_pow(n, p - 1) % mod;
    }
}

ll com(ll n, ll k) {
    if (n < k || n < 0 || k < 0) {
        return 0;
    }
    return fac[n] * rep_pow(fac[k], mod - 2) % mod * rep_pow(fac[n - k], mod - 2) % mod;
}

int main() {
    ll x, y;
    cin >> x >> y;
    init();
    if ((x + y) % 3) {
        cout << 0 << endl;
        return 0;
    }
    ll sm = (x + y) / 3;
    ll a = y - sm;
    ll b = x - sm;
    cout << com(a + b, b) << endl;
    return 0;
}


Measured memory_bytes: 8064
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate など
#include <cassert>    // assert
#include <stdexcept>
using namespace std;

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
// typedef int128_t ll;
// typedef cpp_int ll;

// GCC, 配列のアクセスなど
#define _GLIBCXX_DEBUG
// Clang, 配列のアクセスなど
#define _LIBCPP_DEBUG 0

#define NDEBUG 1
// debug用出力 https://trap.jp/post/998/
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << H << " ";
    debug_out(T...);
}
#ifdef NDEBUG
#define debug(...)
#else
#define debug(...) debug_out(__VA_ARGS__)
#endif

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

// constexpr inline ll MOD = 1'000'000'007;
// constexpr int max_n = 1000000+9;

int n;
multiset<pair<int,int>> poss, negs;

int main()
{
    // 入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >>n;
    REP(i,n) {
        string s; cin>>s;
        int next = 0, down = 0;
        REP(j, s.size())
        {
            next += (s[j] == '(') ? 1 : -1;
            down = min(down, next);
        }
        if (next >= 0)
        {
            poss.insert(make_pair(- down, next)); // down を正に
        }
        else
        {
            negs.insert(make_pair(next - down, - next)); // next - down も - next も >=0
        }
    }


    bool succ = true;
    int h_poss = 0;
    for (auto pa : poss)
    {
        h_poss -= pa.first;
        if (h_poss < 0)
        {
            succ = false;
        }
        h_poss += pa.first + pa.second;
        debug("h_poss", h_poss);
    }

    int h_negs = 0;
    for (auto pa : negs)
    {
        h_negs -= pa.first;
        if (h_negs < 0)
        {
            succ = false;
        }
        h_negs += pa.first + pa.second;
        debug("h_negs", h_negs);
    }

    succ &= (h_poss == h_negs);

    cout << (succ?"Yes":"No") << endl;

    return 0;
}


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

using namespace std;

struct schedule_t {
  int seconds;
  int start;
  int interval;
};

std::vector<int> calc(const std::vector<schedule_t>& ss) {
  int const n = ss.size() + 1;
  std::vector<int> ret;
  for (int i = 0; i < n; i++) {
    int time = 0;
    for (int station = i; station < n - 1; station++) {
      const auto& s = ss[station];
      if (time <= s.start) {
        time = s.start;
      } else {
        time = ((time + s.interval - 1) / s.interval) * s.interval;
      }
      time += s.seconds;
    }
    ret.push_back(time);
  }
  return ret;
}

int main() {
  int n;
  std::cin >> n;
  std::vector<schedule_t> ss(n - 1);
  for (int i = 0; i < n - 1; i++) {
    auto& s = ss[i];
    std::cin >> s.seconds >> s.start >> s.interval;
  }
  for (auto const t : calc(ss)) {
    std::cout << t << std::endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int a[3] = {0};
	rep (i, 3) cin >> a[i];
	sort (a, a + 3);

	cout << (a[0] + a[1] == a[2] || a[0] == a[1] + a[2] ? "Yes" : "No") << endl;
	
	return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end());

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << min(a,b)+min(c,d) << endl;
}

Measured memory_bytes: 256
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
n=int(input())
d=make_divisors(n)
if d[-1]**2==n:
    print(2*d[-1]-2)
else:
    print(d[-1]+d[-2]-2)

Measured memory_bytes: 3268
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    ll a, b, x, cnt;
    cin >> a >> b >> x;
    cnt = b / x - a / x;
    if (a % x == 0) {
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt();
            var N = line[0];
            var i = line[1];

            return N - i + 1;
        }

        public const int mod = 1000000007;
        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc()); static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

    #region Console
    public class ConsoleReader { public virtual string String() => Console.ReadLine(); public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); public ulong ULong() => ulong.Parse(String()); public double Double() => double.Parse(String()); public string[] Split() => String().Split().ToArray(); public int[] SplitInt() => String().Split().Select(int.Parse).ToArray(); public long[] SplitLong() => String().Split().Select(long.Parse).ToArray(); public ulong[] SplitULong() => String().Split().Select(ulong.Parse).ToArray(); public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray(); public IEnumerable<string> Repeat(int count) { for (int i = 0; i < count; i++) yield return String(); } public IEnumerable<int> RepeatInt(int count) { for (int i = 0; i < count; i++) yield return Int(); } public IEnumerable<long> RepeatLong(int count) { for (int i = 0; i < count; i++) yield return Long(); } public IEnumerable<string[]> RepeatSplit(int count) { for (int i = 0; i < count; i++) yield return Split(); } public IEnumerable<int[]> RepeatSplitInt(int count) { for (int i = 0; i < count; i++) yield return SplitInt(); } }
    #endregion
}

Measured memory_bytes: 11348
# -*- coding: utf-8 -*-

s = [input() for _ in range(3)]
turn = 0
while True:
    if len(s[turn]) == 0:
        print('ABC'[turn])
        exit()

    _turn = turn
    turn = ['a', 'b', 'c'].index(s[turn][0])
    s[_turn] = s[_turn][1:]


Measured memory_bytes: 2940
// @prefix atcoder
// @description atcoder template

#include <bits/stdc++.h>
using namespace std;
#define int long long

// typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// rep
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'
#define DEBUGP(x) cerr << #x << ": " << x.first << " \t" << x.second << '\n'

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

    FOR(a, -500, 500) {
        FOR(b, -500, 500) {
            if (pow(a, 5) - pow(b, 5) == x) {
                cout << a << " " << b << endl;
                return 0;
            }
        }
    }

    return 0;
}


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

using namespace std;

const int N = 110;

int n;
string s;

int main()
{
    cin >> n;
    for(int i = 1; i <= 9; i++)
        if(n % i == 0 && n / i <= 9 && n / i >= 1)
        {
            puts("Yes");
            return 0;
        }
    puts("No");
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;
const ll MOD = 998244353;
const ll N = 2e5+2;
ll f[N];
///modulo version
ll binpow(ll a,ll b) {
if (b == 0)return 1;ll res = binpow(a, b / 2)%MOD;
if (b % 2)return ((res%MOD * res%MOD)%MOD * a%MOD)%MOD;else return (res%MOD * res%MOD)%MOD;}

ll inv(ll A)
{
    return binpow(A,MOD-2);
}

//modulo arithmetic
inline ll add(ll a, ll b)
{
	ll res = a + b;
	if(res >= MOD)
		return res - MOD;
	return res;
}

inline ll mult(ll a, ll b)
{
	ll  res = a;
	res *= b;
	if(res >= MOD)
		return res % MOD;
	return res;
}

inline ll sub(ll a, ll b)
{
	return (a%MOD-b%MOD+MOD)%MOD;
}

ll ncr(ll n,ll r)
{
	if(r==0)
        return 1;
    if(n==r)
        return 1;
    return mult(f[n],inv(mult(f[r],f[n-r])));
}

int main()
{
    IOS
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// freopen("error.txt","w",stderr);
 	f[0]=1;
 	f[1]=1;
 	for(ll i=2;i<N;i++)
 	{
 		f[i]=mult(i,f[i-1]);
 	}
 	ll n,m,k;
 	cin>>n>>m>>k;
 	ll ans=0;
 	for(ll i=0;i<=k;i++)
 	{
 		ll m1=ncr(n-1,n-1-i)%MOD;
		ll m2=mult(m,binpow(m-1,n-1-i));
		// cout<<m1<<" "<<m2<<endl;
		ans=add(ans,mult(m1,m2));
 	}
 	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 5228
n = int(input())
s = list(map(int, input().split()))
s.sort()

A = max(s)
dp = [0] * (A + 1)

for ss in s:
    dp[ss] += 1

pairwise = True
setwise = True

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False
    if cnt == n:
        setwise = False
        break

if pairwise:
    print("pairwise coprime")
elif setwise:
    print("setwise coprime")
else:
    print("not coprime")


Measured memory_bytes: 194692
mod = 10**9+7
def comb_mod(n,r,mod,invs):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    ans *= invs[r]
    ans %= mod
    return ans

A, B, C, D = map(int, input().split())

invs = [1]*(C+2)
for i in range(1,C+2):
    invs[i] = invs[i-1]*pow(i,mod-2,mod)
    invs[i] %= mod
ans = comb_mod(C+D+2,C+1,mod,invs)-comb_mod(B+C+1,B,mod,invs)-comb_mod(A+D+1,A,mod,invs)+comb_mod(A+B,A,mod,invs)
print(ans%mod)

Measured memory_bytes: 48108
N, M, = map(int, input().split())
a = set([int(input()) for _ in range(M)])
DP = [0]*(N+2)
num = 1000000007
DP[0] = 1
for i in range(N):
  if i in a:
    DP[i] = 0
  else:
    DP[i] = DP[i] % num 
    if i < N:
      DP[i+1] += DP[i]
      DP[i+2] += DP[i]
print(DP[-2]%num)


Measured memory_bytes: 13192
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	as := make([]int, n)
	am := make(map[int]int)
	sum := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&as[i])
		sum += as[i]
		am[as[i]]++
	}

	var q int
	fmt.Scan(&q)
	var b, c int
	for i := 0; i < q; i++ {
		fmt.Scan(&b, &c)
		p := am[b]
		am[c] += p
		am[b] = 0
		sum -= b * p
		sum += c * p
		fmt.Println(sum)
	}
}


Measured memory_bytes: 10292