akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;} 

int N;
// 連結成分の二部グラフ判定。隣接行列表現
vector<int> seen; // 0未訪問、1黒、-1白
bool dfs(const VVI &G, const int v, const int c = 1) {
    seen[v] = c;

    rep(nv, 1, N+1) {
        if (G[v][nv] == INF || v == nv) continue;
        if (seen[nv] == c) return false; // next_v が探索済みで同色
        if (seen[nv] == 0 && !dfs(G, nv, -c)) return false;
    }
    return true;
}

// warshall-floyd
VVI WF(VVI d){
    int V = d.size();
    //径路 i - k - j 
    rep(k, 1, V) rep(i, 1, V) if (d[i][k] < INF) 
        rep(j, 1, V) if (d[k][j] < INF)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    return d;
}


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

cin >> N;
VVI G(N+1, VI(1, INF)); // 隣接行列
// VS S(N); invec(S);

rep(i, 0, N){
    string S; cin >> S;
    rep(j, 0, N) {
        if (S[j] - '0') G[i+1].push_back(S[j] - '0');
        else if (i == j) G[i+1].push_back(0);
        else G[i+1].push_back(INF);
    }
}

// 二部グラフ判定
seen.assign(N+1, 0);
if (!dfs(G, 1)){
    cout << "-1\n";
    return 0;
}

VVI dist = WF(G);
i64 d = 0;
for(VI d1: dist) for(i64 d2: d1) if (d2 < INF)
    d = max(d, d2);

cout << d + 1 << "\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



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

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

    set <string> s;
    string a;
    int n;
    cin >> n;
    while (n--) {
        cin >> a;
        s.insert(a);
    }
    cout << s.size();
}

Measured memory_bytes: 19272
#include <stdio.h>
const int MAX_V = 1000000;
int prime[MAX_V];
int main() {
  int i, k, v, n, max = 0;
  for(i = 2; i <= MAX_V; i++) {
    prime[i] = 1;
  }
  for(i = 2; i*i <= MAX_V; i++) {
    if(prime[i]){
      for(k = 2 * i; k <= MAX_V; k += i) {
        prime[k] = 0;
      }
    }
  }
  while(1){
    scanf("%d", &n);
    if(n == 0) break;
    for(i = n;i > 0;i--){
      if(prime[i] == 1 && prime[i - 2] == 1){
        max = i;
        break;
      }
    }
  printf("%d %d\n", max - 2, max);
  }
  return 0;
}

Measured memory_bytes: 4936
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200010];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }   
    sort(a,a+n);
    for (int i = 0; i < n - 1; i++) {
        if (a[i] == a[i+1]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    doublecout(abs(polar(a, (h / 6.0 + m / 360.0) * M_PI) - polar(b, m * M_PI / 30.0)));
    return 0;
}


Measured memory_bytes: 4144
#include<stdio.h>
#include<math.h>
#define PI 3.141592
int main()
{
	int a,b;
	double x=0,y=0,r=90.0;
	while(scanf("%d,%d",&a,&b) && a || b)
	{
		y+=a*sin((r/180)*PI);
		x+=a*cos((r/180)*PI);
		r-=b;
	}
	printf("%d\n%d\n",(int)x,(int)y);
	return 0;
}

Measured memory_bytes: 604
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
const long long MOD = (long long)1e9 + 7;

int a, b, c;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> a >> b >> c;
	cout << (b / a > c ? c : b / a) << "\n";
	//system("pause");
	return 0;
}

Measured memory_bytes: 256
a = list(map(int,input().split()))
aa = [[],[],[],[],[],[],[],[]]
for i in range(a[0]):
	e,r,t = map(int,input().split())
	aa[0].append(e+r+t)
	aa[1].append(e+r-t)
	aa[2].append(e-r+t)
	aa[3].append(e-r-t)
	aa[4].append(-e+r+t)
	aa[5].append(-e+r-t)
	aa[6].append(-e-r+t)
	aa[7].append(-e-r-t)
 
for i in range(8):
	aa[i] = sorted(aa[i],reverse = True)
 
su = 0
 
for i in range(8):
	if su < sum(aa[i][0:a[1]]):
		su = sum(aa[i][0:a[1]])
 
print(su)

Measured memory_bytes: 40304
using System;
namespace inonoa{
    class Ino{
        static void Main(){
            string[] r_g_b_n = Console.ReadLine().Split();
            int r = int.Parse(r_g_b_n[0]);
            int g = int.Parse(r_g_b_n[1]);
            int b = int.Parse(r_g_b_n[2]);
            int n = int.Parse(r_g_b_n[3]);
            int ans = 0;
            for(int i=0;i<(n/r)+1;i++){
                for(int j=0;j<(n/g)+1;j++){
                    if((n - i*r - j*g)%b==0 && n-i*r-j*g>=0){
                        ans ++;
                    }
                }
            }
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <cstdint>
#include <string>
int main()
{
  auto input = [](){
    std::string buf;
    std::getline(std::cin, buf);
    return std::stoul(buf);
  };
  const auto n = input();
  std::uint32_t nm1 = 0;
  std::uint32_t nmi1 = 0;
  std::uint32_t nm2 = 0;
  for(std::uint32_t i = 0; i < n; ++i){
    const auto n = input();
    if(nm1 < n){
      nm2 = nm1;
      nm1 = n;
      nmi1 = i;
    } else if (nm2 < n){
      nm2 = n;
    }
  }
  for(std::uint32_t i = 0; i < n; ++i){
    if (i != nmi1){
      std::cout << nm1 << std::endl;
    } else {
      std::cout << nm2 << std::endl;
    }
  }
}

Measured memory_bytes: 1664
/*
 *    FileName:
 *      Source:
 *        Date:
 *      Author: Mew
 *	  Function:
 */
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iomanip>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<iterator>
#include<ctime>
using namespace std;
string s = "CODEFESTIVAL2016";
int main()
{
	string sc;
	cin >> sc;
	int ans = 0;
	for(int i=0;i<16;i++){
		if(s[i] != sc[i])
			ans ++;
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 256
import sys
N=int(sys.stdin.readline().strip())
A=[]
B=[]
for _ in range(N):
    a,b=map(int, sys.stdin.readline().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort()
if N%2==0:
    A_med=float(A[N/2]+A[N/2-1])/2
    B_med=float(B[N/2]+B[N/2-1])/2
    print int((B_med-A_med)*2+1)
else:
    A_med=A[N/2]
    B_med=B[N/2]
    print B_med-A_med+1


Measured memory_bytes: 100840
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;

    if (a == b && b == c) {
        cout << 1 << endl;
    } else if (a != b && a != c && b != c) {
        cout << 3 << endl;
    } else {
        cout << 2 << endl;
    }
    return 0;
}

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

int main (void){
	int n, v[20], c[20];
	int x=0, y=0, i;
	
	cin >> n;

	for (i = 0; i + 1 <= n; i++) {
		cin >> v[i];
	}

	for (i = 0; i + 1 <= n; i++) {
		cin >> c[i];
	}

	for (i = 0; i + 1 <= n; i++) {
		if (v[i] - c[i] >= 0) {
			x = x + v[i];
			y = y + c[i];
		}
	}

	cout << x - y;
}

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

using namespace std;

const int N = 3010;
const int P = 998244353;

int dp[N][N][2]; // 0 - se a primeira coluna nao tem 1, 1 - se a primeira coluna tem 1.

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    dp[a][b][0] = 1;

    for (int i = a; i <= c; ++i) {
        for (int j = b; j <= d; ++j) {
            if (i < c) {
                dp[i+1][j][1] += (dp[i][j][0] * 1ll * j) % P;
                dp[i+1][j][1] += (dp[i][j][1] * 1ll * j) % P;
                dp[i+1][j][1] %= P;
            }
            if (j < d) {
                dp[i][j+1][0] += (dp[i][j][0] * 1ll * i) % P;
                dp[i][j+1][0] += dp[i][j][1] % P; // se tiver duas cores iguais faz corte vertical, caso contrarrio faz corte normal
                dp[i][j+1][0] %= P;
            }
        }
    }
    printf("%lld\n", (dp[c][d][0] + dp[c][d][1]) % P);
}

Measured memory_bytes: 74212
n=int(input())
i=1
count=0
ans=[]
if n==1:
    print(1)
    exit()

while count<n:
    count+=i
    ans.append(i)
    i+=1
    
#print(ans,count)
if count-n!=0:
    a=ans.pop(count-n-1)
for i in range(len(ans)):
    print(ans[i])

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M;
int l[200000],r[200000];
signed main(){
    cin>>N;
    rep(i,N)l[i]=i,r[i]=i+1;

    cin>>M;
    vpint vec;
    rep(i,M){
        int x,y;
        cin>>x>>y;
        y--;
        vec.pb(pint(x,y));
    }
    sort(all(vec));
    rep(i,vec.size()){
        int a=vec[i].se;
        int b=vec[i].se+1;
        l[b]=l[a];
        r[a]=r[b];
    }

    rep(i,N){
        if(i)printf(" ");
        printf("%lld",r[i]-l[i]);
    }
    puts("");

    return 0;
}

Measured memory_bytes: 8016
use v5.18; # strict say state
use warnings;

chomp (my ($r, $g, $b, $n) = split / /, <STDIN>);
my $ans = 0;
for my $i (0..$n) {
  last if $r * $i > $n;
  for my $j (0..$n) {
    last if $r * $i + $g * $j > $n;
    my $c = $n - $r * $i - $g * $j;
    $ans++ if $c % $b == 0 && $c <= $n * $b;
  }
}
say $ans;

Measured memory_bytes: 640
#include<stdio.h>

int main(voud) {
	int cnt = 0, N, K, h[100000];
	scanf("%d %d", &N, &K);

	for(int i = 0; i < N; ++i) {
		scanf("%d", &h[i]);
		if(h[i] >= K) {
			++cnt;
		}
	}
	printf("%d\n", cnt);
}


Measured memory_bytes: 512
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(z) = it.next() {
            Some(it.fold(z, |x, y| min!(x, y)))
        } else {
            None
        }
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(z) = it.next() {
            Some(it.fold(z, |x, y| max!(x, y)))
        } else {
            None
        }
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}


macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let l: usize = sc.cin();
    let r: usize = sc.cin();
    if l + 3000 < r {
        put!(0);
    } else {
        let mut ans = 2018;
        for i in l..r {
            for j in i+1..r+1 {
                ans = min!(ans, (i * j) % 2019);
            }
        }
        put!(ans);
    }
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <algorithm>

#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
typedef long long ll;

using namespace std;

int main(){
    int x, y;
    cin >> x >> y;
    int ans = 2e9;
    rep(i, (1 << 2)){
        bitset<2> b(i);
        int tmp = x;
        int goal = y;
        if(b[0]){
            tmp *= -1;
        }
        if(b[1]){
            goal *= -1;
        }
        if(goal >= tmp){
            // 実現可能.
            ans = min(ans, goal - tmp + b[0] + b[1]);

        }

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


Measured memory_bytes: 256
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10031
#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;

void InputSet(std::vector<int> & a) {
	int n;
	cin >> n;
	a.resize(n,0);
	for(int i=0;i<n;++i) {
		cin >> a.at(i);
	}
	sort(a.begin(),a.end());
}
int main(){
	std::vector<int> S,T;
	::InputSet(S);
	::InputSet(T);
	std::vector<int> intersect = std::vector<int>(min(S.size(),T.size()));
	vector<int>::iterator it = set_intersection(S.begin(),S.end(),T.begin(),T.end(),intersect.begin());

	cout << int(it - intersect.begin()) << std::endl;
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define fasterthanlight ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define test int T; cin>>T; while(T--)
#define endl "\n"
#define int long long
#define vi vector<int>
#define pb push_back
#define mod 1000000007
#define MAX 1e9
#define MIN -1e9
#define hi "visited\n" //sasta debugging
using namespace std;

//author::@whohet-->Het Patel

signed main()
{
	fasterthanlight;
	int a;
	long double b;
	cin >> a >> b;
	int b1 = trunc(a * b);
	//int c1 = b1; //cout << b1 << endl;
	cout << b1;
	//cout << "\n\n"<<"Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " seconds.\n";
	return 0;
}


Measured memory_bytes: 3748
#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 s, w;
    cin >> s >> w;
    if (s <= w) cout << "unsafe" << endl;
    else cout << "safe" << endl;
    return 0;
}


Measured memory_bytes: 3620
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def calc_ar(bx,by,x,y):
    if bx == x:
        if y > by:
            return 1
        else:
            return 3
    else:
        if x > bx:
            return 0
        else:
            return 2

while True:
    N = inp()
    if N == 0:
        break
    else:
        lines = []

        for _ in range(N+1):
            m = inp()
            xys = [inpl() for _ in range(m)]

            dd = []
            for i in range(1,m):
                bx,by = xys[i-1]
                x,y = xys[i]
                if x == bx:
                    dd.append(abs(y-by))
                else:
                    dd.append(abs(x-bx))

            ar = []
            for i in range(2,m):
                x0,y0 = xys[i-2]
                x1,y1 = xys[i-1]
                x2,y2 = xys[i]
                ar01 = calc_ar(x0,y0,x1,y1)
                ar12 = calc_ar(x1,y1,x2,y2)
                ar.append((ar12 - ar01)%4)

            lines.append([dd]+[ar])


        for i in range(1,N+1):
            dd,ar = lines[i]
            if lines[0] == [dd]+[ar]:
                print(i)
            else:
                dd = list(reversed(dd))
                ar = [(a+2)%4 for a in reversed(ar)]
                if lines[0] == [dd]+[ar]:
                    print(i)



        print('+++++')



Measured memory_bytes: 7176
def dfs x, y
  if !@lines[y] || @lines[y][x] == 0
    # p [x, y, false]
    return
  end
  # p [x, y, true]
  @lines[y][x] = 0

  dfs x + 1, y
  dfs x + 1, y + 1
  dfs x + 1, y - 1
  dfs x, y + 1
  dfs x, y - 1
  dfs x - 1, y
  dfs x - 1, y + 1
  dfs x - 1, y - 1
end

loop do
  w, h = gets.split.map(&:to_i)
  break if w == 0
  @lines = [[0] * (w+2)]
  h.times do
    @lines << [0, *gets.split.map(&:to_i), 0]
  end
  @lines << [0] * (w+2)

  ans = 0
  visited = []
  @lines.each_with_index do |l, y|
    next if y == 0 || y == h + 1
    l.each_with_index do |c, x|
      next if x == 0 || x == w + 1
      if @lines[y][x] == 1
        dfs x, y
        ans += 1
      end
    end
  end

  puts ans
end

Measured memory_bytes: 9232
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
long long  mod = 1000000007;
long long A[100010], B[100010];
int main()
{
	int N;
	long long an = 0;
	cin >> N;
	for (int i = 0; i < N + 1; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}
	for (int i = 0; i < N; i++) {
		if (B[i] > A[i]) {
			an += A[i];
			B[i] -= A[i];
			A[i] = 0;
			if (B[i] > A[i + 1]) {
				an += A[i + 1];
				A[i + 1] = 0;
			}
			else {
				an += B[i];
				A[i + 1] -= B[i];
			}
		}
		else {
			an += B[i];
			A[i] -= B[i];
		}
	}
	cout << an;
}

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

#define MEM(a, b) memset(a, (b), sizeof(a))
#define PI 3.1415926535897932384626433832795
#define endl '\n'
#define exists(s, e) (s.find(e)!=s.end())
#define WHILE(n)
#define pb push_back
#define f first
#define s second
#define UNI(vec) vec.erase(std::unique(vec.begin(), vec.end()),vec.end());
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::pair<int, pii> piii;

const int INF = 0x3f3f3f3f;
#define MAXN 101 * 1001
using namespace std;
int n,m,ans;
ll dp[MAXN];

int main(){
    MEM(dp,INF);
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    dp[0] = 0;
    for (int i =0,a,b; i < n; i++){
        cin>>a>>b;
        for(int j = MAXN -1-b; j >=0; j--){
            dp[j+b] = min(dp[j+b], dp[j] + a);
        }
    }
    for(int i = 0; i < MAXN; i++){
        if(dp[i] <= m){
            ans = i;
        }
    }
    cout<<ans;



}


Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <limits>
#include <numeric>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <stack>

using namespace std;

#define INFint (1<<30)
#define BOUND 27182818284
#define MAT 2

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

ll MOD = 1000000007;
const ll INF = (1ll<<60);
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for(int i=int(a);i<int(b);++i)

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

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

// gcd
template<typename T>
T gcd(T a, T b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

int findGCD(vector<int> arr) {
    int result = arr[0];
    for (auto a: arr) {
        result = gcd(a, result);
    }
    return result;
}

template<typename T>
T lcm(T m, T n) {
    // 引数に0がある場合は0を返す
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    fill((T *) array, (T *) (array + N), val);
}


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

// v.front() = -BOUND;
// v.back() = BOUND;

//struct edge{
//    int cost, to;
//
//    edge(int in_cost, int in_to){
//        cost=in_cost;
//        to=in_to;
//    }
//    bool operator<(const edge &a) const
//    {
//        return cost > a.cost;
//    }
//};
int next_to[210000][26];

int main() {
    string S,T; cin >> S >> T;
    string SS=S+S;

    Fill(next_to, INFint);

    int point[26];
    Fill(point, INFint);
    for(int i=SS.size()-1; i>=0; i--){
        for(int j=0; j<26; j++){
            next_to[i][j]=point[j];
        }
        point[SS[i]-'a']=i;
    }

    int first_c[26];
    Fill(first_c, INFint);

    for(int i=0; i<S.size(); i++){
        first_c[S[i]-'a']=min(i,first_c[S[i]-'a']);
    }

    ll ans=1LL;
    int now=0;
    if(T[0]!=S[0]) {
        ans += next_to[now][T[0] - 'a'];
        now=next_to[now][T[0] - 'a'];
    }

    if(now==INFint){
        cout << -1 << endl;
        return 0;
    }

    for(int i=1; i<T.size(); i++){
        if(next_to[now][T[i]-'a'] != INFint){
            ans+=(next_to[now][T[i]-'a']-now);
            now=(next_to[now][T[i]-'a']);
            if(now>=S.size()){
               now-=S.size();
            }
        }else{
            cout << -1 << endl;
            return 0;
        }
    }

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

Measured memory_bytes: 22144
#include<bits/stdc++.h>
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 sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }
struct INF { template<class T> operator T() { return numeric_limits<T>::max() / 2; } } INF;


int main(){

    int n;
    cin >> n;
    V<bool> ok(n);
    rep(i,n) {
        int a, b;
        cin >> a >> b;
        ok[i] = (a==b);
    }

    bool ans = false;
    for(int i = 1; i < n-1; i++) {
        ans |= (ok[i-1] && ok[i] && ok[i+1]);
    }
    
    YesorNo(ans);
}

Measured memory_bytes: 3724
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long int;

int main() {
	LL N, M;
	cin >> N >> M;
	LL l = 1, u = N;
	int m = 0;
	if (N % 2 == 1) {
		while (m < M) {
			cout << l << " " << u << endl;
			m++;
			l++;
			u--;
		}
	}
	else {
		l = 1;
		bool over_half = false;
		while (m < M) {
			if ((u - l) * 2 <= N && over_half == false) {
				over_half = true;
				u--;
			}
			cout << l << " " << u << endl;
			m++;
			l++;
			u--;
			

		}


	}
	return 0;

}

Measured memory_bytes: 3604
from collections import deque
N=int(input())
color=["white"]*(N+1)
rinsetu=[[] for i in range(N+1)]
for i in range(N):
    a,*b=list(map(int,input().split()))
    for idx,j in enumerate(b):
        if idx==0:continue
        rinsetu[a].append(j)
distance=[10**5]*(N+1)
distance[1]=0
def bfs():
    d = deque()
    d.append(1)
    while(d):
        num=d.popleft()
        color[num] = "black"
        for i in rinsetu[num]:
            if color[i]=="white":
                d.append(i)
                distance[i]=min(distance[num]+1,distance[i])

bfs()
for i in range(1,N+1):
    if distance[i]==10**5:distance[i]=-1
    print(i,distance[i])


Measured memory_bytes: 6380
N, K = map(int, input().split())
A = list(map(int, input().split()))
mA, nA = [], []
for a in A:
    if a < 0:
        mA.append(a)
    else:
        nA.append(a)
mA = sorted(mA)[::-1]
nA = sorted(nA)
lnA = len(nA)
lmA = len(mA)


def F(k):
    # k以下の数
    # positive positive
    r = 0
    i, j = 0, lnA-1
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # negative negative
    i, j = 0, lmA-1
    while i < lmA:
        while j >= 0 and mA[j]*mA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # positive negative
    i, j = 0, lmA-1
    while i < lnA:
        while j >= 0 and mA[j]*nA[i] <= k:
            j -= 1
        r += 2*(lmA-j-1)
        i += 1
    for a in A:
        if a*a <= k:
            r -= 1
    return r//2


mx, mn = 2*10**18, -2*10**18
idx = (mx+mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        mn = idx
    else:
        mx = idx
    idx = (mx+mn)//2
print(idx+1)


Measured memory_bytes: 99796
n,m = map(int,input().split())
a=input().split()
a_int = [int(i) for i in a]

su = 0
mm = 0

for k in range(n):
    su += a_int[k]

bor = su*1/(4*m)

for j in range(n):
    if a_int[j] >= bor:
        mm += 1

if mm >= m:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
X = int(input())

# for n in range(1000000):
#     # print((n * (n - 1) // 2))
#     if (n * (n - 1) // 2) >= X:
#         break


# n^2 - n - 2X <= 0
# n = (1 + sqrt(1 + 8X)) // 2
n = max(int((1 + (1 + 8 * X) ** 0.5) / 2) - 1, 0)
while True:
    if (n * (n - 1) // 2) >= X:
        break
    n += 1
print(n - 1)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int N, X;
    cin >> N >> X;

    vector<int> m(N);

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

    int sum = 0;        //１つずつ作った場合の合計
    int min = 1000;     //1つ作るのに必要な材料の最小値

    for(int i=0; i<N; i++)
    {
        sum += m.at(i);

        if( m.at(i) < min )
        {
            min = m.at(i);
        }
    }

    int add = (X - sum) / min;
    cout << (N + add);

    return 0;
}

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

#define dbg(x) cerr<<#x": "<<x<<"\n"
#define dbg_p(x) cerr<<#x": "<<x.first<<","<<x.second<<"\n"
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

#define st first
#define nd second

#define DMAX 55

using namespace std;

long long n, k, a[DMAX], b[DMAX], c[DMAX];
bool dp[DMAX], ok = true;

template<class T>
ostream& operator<<(ostream& out, vector<T> v) {
	out << v.size() << '\n';
	for(auto e : v) out << e << ' ';
	return out;
}

bool can(long long mask) {

	for(int i = 1; i <= n; i++) {
		memset(dp, 0, sizeof dp);
		dp[a[i]] = 1;
		for(int k = 50; k > 0; k--) {
			if((mask & (1LL << k)) == 0) continue;

			for(int j = a[i]; j > 0; j--)
				dp[j % k] |= dp[j];
		}
		if(dp[b[i]] == 0) 
			return 0;
	}
	return 1;
}

bool zero() {
	for(int i = 1; i <= n; i++)
		if(a[i] != b[i]) return 0;
	return 1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;

	for(int i = 1; i <= n; i++) 
		cin >> a[i];
	for(int i = 1; i <= n; i++) 
		cin >> b[i];

	if(zero()) {
		cout << "0\n";
		return 0;
	}

	long long msk = (1LL << 51LL);
	msk--;

	if(!can(msk)) {
		cout << "-1\n";
		return 0;
	}
	for(int i = 50; i >= 0; i--) {
		msk ^= (1LL << i);
		// dbg(msk);
		if(!can(msk)) {
			// dbg_ok;
			msk ^= (1LL << i);
		}
		// dbg(msk);

	}
	cout << msk << '\n';
}

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

int x ;
int n , p[105] ;
bool have[205] ;

int main()
{
	scanf("%d%d" ,&x , &n) ;
	for ( int i = 1 ; i <= n ; i++ ) scanf("%d" , &p[i]) , 
		have[p[i]] = true ;
	for ( int d = 0 ; ; d++ )
	{
		if ( x >= d && ! have[x - d] ) 
			{
				printf("%d\n" , x - d) ;
				return 0 ;
			}
		if ( ! have[x + d] ) 
			{
				printf("%d\n" , x + d) ;
				return 0 ;
			}
	}
	return 0 ;
}

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

int main()
{
    int N;
    cin >> N;
    int min = INT_MAX;
    int max = 0;
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        if (tmp < min) { min = tmp; }
        if (max < tmp) { max = tmp; }
    }
    // cout << min << " " << max << "\n";
    cout << max - min;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstdlib>
#define INF 100000000
#define _INF -100000000
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;

static const int N = (int)1e5;

int n, L;
vi a(N);

void tie(int x) {
	stack<int> stk;
	stk.push(x + 1); //出力番号をプッシュ
	Loopr(i, x) {
		stk.push(i + 1);
	}
	for (int i = x + 1;i < n - 1;i++) {
		stk.push(i + 1);
	}
	while (stk.size()) {
		int y = stk.top(); stk.pop();
		cout << y << endl;
	}
}

void solve() {
	bool judge = false;
	Loop(i, n - 1) {
		if (a[i] + a[i + 1] >= L) {
			judge = true;
			cout << "Possible" << endl;
			tie(i);
			break;
		}
	}
	if (!judge) cout << "Impossible" << endl;
}

int main() {
	cin >> n >> L;
	Loop(i, n) {
		cin >> a[i];
	}
	solve();
	return 0;
}

Measured memory_bytes: 1616
#include <iostream>
#include <sstream>

int main() {
    int H, W;
    std::stringstream ss;
    while (std::cin >> H >> W) {
        if (H == 0 && W == 0) break;
        else {
            for (int i=0;i<H;i++) {
                for (int j=0;j<W;j++)
                    if (i == 0 || j == 0 || i == H-1 || j == W-1)
                        ss << "#";
                    else
                        ss << ".";
                ss << "\n";
            }
            ss << "\n";
        }
    }

    std::cout << ss.str();
    
    return 0;
}


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

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    if (n == x) {
        cout << "Yes" << '\n';
        for (int i=1; i<2*n; i++) cout << i << '\n';
    } else if (1 < x && x < 2*n - 1) {
        cout << "Yes" << '\n';
        int i=2;
        for ( ; i<n; i++) 
            cout << i + (i >= x) << '\n';
        cout << 1 << '\n' 
             << x << '\n'
             << 2*n - 1 << '\n';
        for ( ; i+2<2*n; i++) 
            cout << i + (i >= x) << '\n';
    } else
        cout << "No" << '\n';
    return 0;
}

Measured memory_bytes: 1536
while True:
    n, k = map(int, input().split())
    
    if n==0 and k==0 :
        break
    
    slist = []
    alist = []
    s = 0
    for i in range(k):
        a = int(input())
        alist.append(a)
        s += a
    slist.append(s)
    
    for i in range(n-k):
        a = int(input())
        alist.append(a)
        s = slist[i]+a-alist[i]
        slist.append(s)
    
    print(max(slist))
    continue


Measured memory_bytes: 11580
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=a;i<=n;++i)
#define lpd(i,a,n) for(int i=a;i>=n;--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 100002;
int n,m,x[N],y[N],s[N],l[N],ms[N];
vector<pii> g[N];
bool v[N];
ll val[N];

void bfs(int x){
    mem(v, 0);
    queue<int> q;
    v[1] = true;
    q.push(1);
    val[1] = x;
    while(sz(q)){
        int i = q.front(); q.pop();
        for(pii j : g[i]) if(!v[j.f]){
            v[j.f] = true;
            l[j.f] = l[i] + 1;
            val[j.f] = j.s - val[i];
            q.push(j.f);
        }
    }
}

int main(){
    read2i(n,m);
    lp(i,1,n) ms[i] = infi;
    lp(i,1,m){
        read3i(x[i],y[i],s[i]);
        g[x[i]].pb({y[i], s[i]});
        g[y[i]].pb({x[i], s[i]});
        ms[x[i]] = min(ms[x[i]], s[i]);
        ms[y[i]] = min(ms[y[i]], s[i]);
    }

    bfs(1);
    lp(i,1,n) l[i] &= 1;

    si need;
    lp(i,1,m){
        if(l[x[i]] == l[y[i]]){
            ll d = s[i] - (val[x[i]] + val[y[i]]);
            if(d & 1) return cout <<0, 0;
            else need.insert((l[x[i]] ? -d : d) / 2);
        }
        else if(val[x[i]] + val[y[i]] != s[i]) return cout <<0, 0;
    }
    if(sz(need) > 1) return cout <<0, 0;
    if(sz(need) == 1){
        bfs(1 + *need.begin());
        lp(i,1,m) if(val[x[i]] <= 0 or val[y[i]] <= 0 or val[x[i]] + val[y[i]] != s[i])
            return cout <<0, 0;
        return cout <<1, 0;
    }

    ll mxSt = -infll, mnEnd = infll;
    lp(i,1,n){
        ll f,s;
        if(l[i]) f = val[i] - 1, s = val[i] - ms[i] + 1;
        else f = 1 - val[i], s = ms[i] - 1 - val[i];
        if(f > s) swap(f, s);
        mxSt = max(mxSt, f);
        mnEnd = min(mnEnd, s);
    }
    cout <<max(0ll, mnEnd - mxSt + 1);
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/


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



int main() {
int r,D,x2000;
  cin>>r>>D>>x2000;
  vector<int> vec(12);
  vec[0]=x2000;
  for(int i =0;i<10;i++){
    vec[i+1]=vec[i]*r-D;
    cout<<vec[i+1]<<endl;;
  }

}


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

int main(){
  int n,m;
  cin>>n>>m;
  vector<pair<int,int>> a(m);
  for(int i=0; i<m; i++)cin>>a.at(i).first>>a.at(i).second;

  set<int> idx;
  for(int i=0; i<m; i++)if(a.at(i).first==1)idx.insert(a.at(i).second);

  bool flg=false;
  for(int i=0; i<m; i++){
    if(idx.find(a.at(i).first)!=idx.end() && a.at(i).second==n){
      flg=true;
      break;
    }
  }

  if(flg)cout<<"POSSIBLE"<<endl;
  else cout<<"IMPOSSIBLE"<<endl;
  
}

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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

int main() {
  string s;
  cin >> s;
  sort(s.begin(), s.end());
  cout << (s == "abc" ? "Yes" : "No") << endl;
}



Measured memory_bytes: 764
#include <cstdio>
#include <algorithm>
#define maxn 100010
using namespace std;
typedef long long ll;
int n,A,B;
struct node {
	int x,id;
} d[maxn];
ll s1,s2;
bool cmp(node a,node b) {
	return a.x<b.x;
}
int dis(int a,int b) {
	if (a<b)
		return b-a;
	else return a-b;
}
ll cost(int a,int b) {
	return min((ll)dis(a,b)*A,(ll)B);;
}
int main() {
	scanf("%d %d %d",&n,&A,&B);
	for (int i=1;i<=n;i++) {
		scanf("%d",&d[i].x);
		d[i].id=i;
	}
	sort(d+1,d+(n+1),cmp);
	int t;
	for (int i=1;i<=n;i++)
		if (d[i].id==1) {
			t=i;
			break;
		}
	s1=0;
	for (int i=t;i>=2;i--)
		s1+=cost(d[i].x,d[i-1].x);
	s1+=cost(d[1].x,d[t+1].x);
	for (int i=t+1;i<n;i++)
		s1+=cost(d[i].x,d[i+1].x);
	s2=0;
	for (int i=t;i<n;i++)
		s2+=cost(d[i].x,d[i+1].x);
	s2+=cost(d[n].x,d[t-1].x);
	for (int i=t-1;i>=2;i--)
		s1+=cost(d[i].x,d[i-1].x);
	printf("%lld\n",min(s1,s2));
	return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n; cin>>n;
    cout << n*n*n << "\n";
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int INF (1<<30);

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

  int modx = X % 100;
  int divx = X / 100;

  if (modx <= 5*divx) cout << 1 << endl;
  else cout << 0 << endl;

  return 0;
}


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

using namespace std;

#define REP(var, n)  for (int var = 0; var < (n); var++)
#define RREP(var, n)  for (auto var = n - 1; var != static_cast<int>(-1); var--)
#define FOR(var, a, b)  for (auto var = (a); var < (b); var++)
#define RFOR(var, a, b)  for (auto var = b - 1; var != a; var--)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;

#define all(c) begin(c),end(c)

#define D(x) do { std::cerr << x << " "; } while (0)
#define D2(x) do { std::cerr << #x << ": " << x << std::endl; } while (0)


template<typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
    if (!v.empty()) {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}


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


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

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

const int MOD = 1e9 + 7;

auto solve() {
    int N;
    cin >> N;
    string s;
    cin >> s;

    vvll dp(N, vll(N + 1, 0));
    REP(i, N) dp[0][i] = 1;

    REP(i, N - 1) {
        if (s[i] == '<') {
            REP(j, N - i - 1) {
                if (j == 0) dp[i + 1][j] = dp[i][j];
                else dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j]) % MOD;
            }
        } else {
            RREP(j, N) {
                dp[i + 1][j] = (dp[i + 1][j + 1] + dp[i][j + 1]) % MOD;
            }
        }
    }

    return dp[N - 1][0];
}


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

//    cout << (solve() ? "Heisei" : "TBD") << endl;
//    cout << (solve() ? "YES" : "NO") << endl;
    cout << solve() << endl;
//    solve();

    return 0;
}

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

int main(){
  int n;
  cin>>n;
  n=n%1000;
  if(n==0){
    cout<<0<<endl;
  }else{
    cout<<1000-n<<endl;
  }

  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

  ll n, h, w;
  cin >> n >> h >> w;

  vector<ll> a(n), b(n);
  int ans = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];

    ans += min(a[i] / h, b[i] / w);
  }

  cout << ans << ln;

  return 0;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define loop(n) FOR(i,0,n)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {

	int n, Q; cin >> n >> Q;
	vector<LL> a(n);
	for (int i = 0; i < n; i++)cin >> a[i];

	for (int i = 0; i < Q; i++) {
		LL x; cin >> x;

		LL res = 0;

		int right = 0;

		LL sum = 0;

		for (int left = 0; left < n; left++) {

			

			while (right < n && sum + a[right] <= x) {
				sum += a[right];
				right++;
			}

			res += (right - left);

			if (right == left) {
				right++;
			}
			else {
				sum -= a[left];
			}
			
		}

		cout << res << endl;
	}

	return 0;
}


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

using namespace std;

const int mod = 1000000007;
char str[200050];
int dp[200050];
int nxt[200050][2];

int main()
{
	scanf("%s",str + 1);
	int n = strlen(str + 1);
	bool fg = 0;
	for(int i = 1;i < n; ++ i)
		fg |= str[i] == str[i + 1];
	if(!fg) return printf("1\n"),0;
	dp[n + 1] = 1;
	int sum = 0;
	for(int i = n;i >= 1; -- i)
	{
		sum = (sum + str[i] - 'a' + 1) % 3;
		nxt[i][0] = (str[i] == 'a') ? i + 1 : (str[i + 1] == 'b' ? i + 2 : nxt[i + 2][0]);
		nxt[i][1] = (str[i] == 'b') ? i + 1 : (str[i + 1] == 'a' ? i + 2 : nxt[i + 2][1]);
		dp[i] = (dp[nxt[i][0]] + dp[nxt[i][1]] + (sum == 0)) % mod;
	}
	printf("%d\n",dp[1] - (sum == 0));
}

Measured memory_bytes: 5012
a,b,c,d = input().split()

a = int(a)
b = int(b)
c = int(c)
d = int(d)

if abs(a-c)<=d:
    print("Yes")
    exit()

if abs(a-b)<=d:
    if abs(b-c)<=d:
        print("Yes")
    else:
        print("No")
else:
    print("No")


Measured memory_bytes: 3060
ss = input().split()
while ss:
	a,b,c,d,e,f = map(int, ss)
	# A = [[a,b],[d,e]]
	C = [c,f]
	detA = a*e - b*d
	if detA == 0: raise # det(A) == 0.
	At = [[e,-b],[-d,a]]
	x = sum(map((lambda x,y: x*y), At[0], C)) / detA
	y = sum(map((lambda x,y: x*y), At[1], C)) / detA
	fx,fy = '{0:.3f}'.format(x), '{0:.3f}'.format(y)
	if fx == '-0.000': fx = fx[1:]
	if fy == '-0.000': fy = fy[1:]
	print('{0} {1}'.format(fx,fy))
	try: ss = input().split()
	except EOFError: break


Measured memory_bytes: 7632
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        FastReader in = new FastReader();
        FastWriter out = new FastWriter();
        int c = in.nextInt();
        out.pl(c>=30?"Yes":"No");
        out.close();
    }
}
class FastReader{ 
    BufferedReader br; 
    StringTokenizer st; 
    public FastReader() { 
        br = new BufferedReader(new InputStreamReader(System.in)); 
    } 
    String next(){ 
        while (st == null || !st.hasMoreElements()) { 
            try{ 
                st = new StringTokenizer(br.readLine()); 
            }catch (IOException  e){ 
                e.printStackTrace(); 
            } 
        } 
        return st.nextToken(); 
    } 
    int nextInt(){ 
        return Integer.parseInt(next()); 
    } 
    long nextLong(){ 
        return Long.parseLong(next()); 
    } 
    double nextDouble(){ 
      return Double.parseDouble(next()); 
    } 
    String nextLine(){ 
        String str = ""; 
        try{ 
            str = br.readLine(); 
        } 
        catch (IOException e){ 
            e.printStackTrace(); 
        } 
        return str; 
    } 
}
class FastWriter{
    PrintWriter out;
    FastWriter(){
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	out.flush();
    }
    void pl(Object o){
        out.write(o.toString());
	    out.write("\n");
        out.flush();
    }
    void pl(){
        out.write("\n");
    }
    void p(Object o){
        out.write(o.toString());
    }
    void close(){
        out.flush();
        out.close();
    }  
}


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

int main()
{
  string s;
  cin >> s;
  for(int i= 0; i < s.size(); i+=2) cout << s[i];
  cout << endl;
  system("pause");
}

Measured memory_bytes: 760
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    A=list(map(int,input().split()))
    ac=Counter(A)
    #1個がi個，2個がj個，3個がk個
    dp=[[[0.0]*(n+1) for j in range(n+1)]for i in range(n+1)]
    max_i,max_j,max_k=ac[1],ac[2],ac[3]
    for k in range(max_k+1):
        for j in range(max_j+max_k+1):
            for i in range(min(max_i+max_j+max_k+1,n-(j+k)+1)):
                if i+j+k==0:continue
                res=n
                if i>0:res+=dp[i-1][j][k]*i
                if j>0:res+=dp[i+1][j-1][k]*j
                if k>0:res+=dp[i][j+1][k-1]*k
                res/=i+j+k
                dp[i][j][k]=res
    print(dp[max_i][max_j][max_k])

if __name__=='__main__':
    main()

Measured memory_bytes: 255240
package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

func f(x int) int {
	if x == 0 {
		return 0
	}
	return f(x%bits.OnesCount32(uint32(x))) + 1
}

func main() {
	var n int
	var s string
	fmt.Scan(&n)
	fmt.Scan(&s)
	x := make([]int, n)
	for i, c := range s {
		x[i] = int(c - '0')
	}
	// popcount(X0)
	pc := 0
	for _, v := range x {
		pc += v
	}
	pc0 := pc + 1
	pc1 := pc - 1

	xr := [2]int{}
	r := make([][2]int, n)
	k0 := 1
	k1 := 1
	for i := n - 1; i >= 0; i-- {
		if x[i] == 1 {
			xr[0] += k0
			xr[0] %= pc0
			if pc1 > 0 {
				xr[1] += k1
				xr[1] %= pc1
			}
		}
		r[i][0] = k0
		r[i][1] = k1
		k0 = (2 * k0) % pc0
		if pc1 > 0 {
			k1 = (2 * k1) % pc1
		}
	}

	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()
	ans := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		var xi int
		if x[i] == 1 {
			if pc == 1 {
				ans[i] = 0
				continue
			}
			xi = (xr[1] - r[i][1] + pc1) % pc1
		} else {
			xi = (xr[0] + r[i][0]) % pc0
		}
		ans[i] = f(xi) + 1
	}
	for _, v := range ans {
		fmt.Fprintln(w, v)
	}
}


Measured memory_bytes: 10260