akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pr;
typedef vector<pr> vp;
typedef vector<vp> vpp;
typedef vector<vector<ll> > graph;
#define pb push_back
#define mp make_pair
#define maxi INT_MAX
#define mini INT_MIN
#define endl '\n'
void set_val(vector<ll>& v, ll val){for(ll i=0;i<v.size();i++) v[i]=val;}

ll mod = pow(10,9) + 7;
ll modulo = 998244353;
ll i_mov[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
ll j_mov[8] = {1, 1, 1, 0, -1, -1, -1, 0};

vector<vector<int>> g;
vector<int> parent, depth, subsize;

ll power(ll a, ll n)
{
    if(n==0)
    return 1;
    ll temp = power(a,n/2);
    if(n%2==0)
    return (temp*temp)%mod;
    return (((temp*temp)%mod)*a)%mod;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // cout<<fixed;
    // cout<<setprecision(18);
    int n;
    cin>>n;
    string s;
    cin>>s;
    map<char, int> m;
    m['R'] = 0;
    m['G'] = 1;
    m['B'] = 2;
    ll ans = 0;
    vector<vector<int>> dp(n, vector<int>(3, 0));
    dp[0][m[s[0]]]=1;
    for(int i=1;i<n;i++)
    {
        dp[i][0] = dp[i-1][0];
        dp[i][1] = dp[i-1][1];
        dp[i][2] = dp[i-1][2];
        dp[i][m[s[i]]]++;
    }
    for(int i=1;i<n-1;i++)
    {
        int t = (m[s[i]]+1)%3;
        int l = (m[s[i]]+2)%3;
        ans += dp[i][t]*(dp[n-1][l] - dp[i][l]);
        ans += dp[i][l]*(dp[n-1][t] - dp[i][t]);
    }
    // for(int i=0;i<n;i++)
    // cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl;
    for(int i=1;i<n-1;i++)
    {
        for(int k=1;i-k>=0 && i+k<n;k++)
        {
            if(s[i]!=s[i-k] && s[i] != s[i+k] && s[i-k] != s[i+k])
            ans--;
        }
    }
    cout<<ans<<endl;
    
    
    
} 

Measured memory_bytes: 3844
//-----------------------
// author : xyqkoala
// time : 2020-08-29
//-----------------------

#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;

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

void solve();


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


void solve(){
	int n;cin>>n;
	vector<int> nums(n);
	for(int i=0;i<n;i++) cin>>nums[i];
	int tcnt = nums[0];
	for(auto &item:nums){
		tcnt = gcd(tcnt,item);
	}
	if(tcnt!=1){
		cout<<"not coprime"<<endl;
		return;
	}
	unordered_set<int> t;
	bool f = true;
	for(auto item:nums){
		int tn = item;
		for(int i=2;(i*i)<=tn;i++){
			if(tn%i) continue;
			if(t.count(i)){
				f = false;
				break;
			}
			t.insert(i);
			while(tn%i==0){
				tn=tn/i;
			}
		}
		if(!f) break;
		if(tn>1){
			if(t.count(tn)){
				f = false;
				break;
			}
			t.insert(tn);
		}
		if(!f) break;
	}
	if(f){
		cout<<"pairwise coprime"<<endl;
	}else{
		cout<<"setwise coprime"<<endl;
	}
}


Measured memory_bytes: 7168
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/







int A, B;
vector<string> S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B;
    A--; B--;

    {
        string s = "";
        rep(x, 0, 100) s += ".";
        S.push_back(s);

        rep(i, 0, 10) {
            int y = 1 + i * 2;
            string s = "";
            rep(x, 0, 50) {
                s += ".";
                if (B) {
                    s += "#";
                    B--;
                }
                else s += ".";
            }
            S.push_back(s);
            s = "";
            rep(x, 0, 100) s += ".";
            S.push_back(s);
        }
    }
    
    {
        string s = "";
        rep(x, 0, 100) s += "#";
        S.push_back(s);

        rep(i, 0, 10) {
            int y = 1 + i * 2;
            string s = "";
            rep(x, 0, 50) {
                s += "#";
                if (A) {
                    s += ".";
                    A--;
                }
                else s += "#";
            }
            S.push_back(s);
            s = "";
            rep(x, 0, 100) s += "#";
            S.push_back(s);
        }
    }

    int n = S.size();
    printf("%d %d\n", n, 100);
    rep(y, 0, n) printf("%s\n", S[y].c_str());
}

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

using namespace std;

int main(){
  int N, X, Y;
  cin >> N >> X >> Y;

  vector<int> count(N, 0);
  vector<vector<int>> link(N, vector<int>()); 
  for(int i=0; i<N; i++){
    queue<pair<int, int>> q;
    unordered_set<int> passed;
    q.push(make_pair(i, 0));
    passed.emplace(i);
    while(!q.empty()){
      auto cur = q.front();
      q.pop();
      ++count[cur.second];
      
      vector<int> next = {cur.first-1, cur.first+1};
      if (cur.first == X-1) next.emplace_back(Y-1);
      if (cur.first == Y-1) next.emplace_back(X-1);

      for(auto &elem : next){
        if (elem < 0 || elem >= N) continue;
        if (passed.find(elem) != passed.end()) continue;
        q.push(make_pair(elem, cur.second+1));
        passed.emplace(elem);
      }
    }
  }
  
  for(int i=1; i<N; i++){
    cout << count[i]/2 << endl; 
  }
  
  return 0;
}

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

#define REP(i,p,n) for(ll i=p;i<ll(n);++i)
#define rep(i,n) REP(i,0,n)

using ll = long long;
using pll = pair<ll, ll>;

const ll MAXN = 1000001;
bool P[MAXN];
bool S[MAXN];

template<typename T> T gcdraw(T a, T b) { return a ? gcdraw(b%a, a) : b; }
template<typename T> T gcd(T a, T b)
{
    const auto aa = abs(a), bb = abs(b);
    return aa > bb ? gcdraw(aa, bb) : gcdraw(bb, aa);
}

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

    vector<ll> A(N);
    rep (i, N) { cin >> A[i]; }

    vector<ll> PS = { 1, 2 };
    for (ll i=3;i*i<=MAXN;i+=2) if (!P[i])
    {
        for (ll j=2*i;j*j<=MAXN;j+=i) { P[j] = true; }
        PS.emplace_back(i);
    }

    bool isPairwise = true;

    ll cur = A[0];

    for (ll i=0;i<N;++i)
    {
        if (isPairwise) for (const auto& p: PS)
        {
            if (A[i] < p * p) { break; }
            if (A[i] % p) { continue; }

            const auto x = p;
            const auto y = A[i] / p;

            if (x != 1 && S[x]) { isPairwise = false; }
            if (y != 1 && S[y]) { isPairwise = false; }

            S[x] = true;
            S[y] = true;
        }

        cur = gcd(cur, A[i]);
    }

    const auto isSetwise = cur == 1;

    if (isPairwise)     { cout << "pairwise coprime" << endl; }
    else if (isSetwise) { cout << "setwise coprime" << endl; }
    else                { cout << "not coprime" << endl; }

    return 0;
}


Measured memory_bytes: 11116
#include <bits/stdc++.h>
#define mk make_pair
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int a[N];
ll ans, fac[N], inv[N], sum[N];
ll Pow(ll a, int x) {
	ll res = 1;
	while (x) {
		if (x & 1) (res *= a) %= mod;
		(a *= a) %= mod;
		x >>= 1;
	}
	return res;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		sum[i] = sum[i - 1] + a[i];
		sum[i] %= mod;
	}
	fac[0] = 1;
	for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % mod;
	for (int i = 1; i < n; ++i) {
		ll tmp = fac[n] * Pow(i + 1, mod - 2) % mod;
		(ans += tmp * (sum[n - i] + sum[n] - sum[i])) %= mod;
	}	
	(ans += sum[n] * fac[n]) %= mod;
	cout << ans;
} 

Measured memory_bytes: 4096
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	pp := make([]int, n)
	qq := make([]int, n)
	for i := 0; i < n; i++ {
		pp[i] = getNextInt(scanner)
	}
	for i := 0; i < n; i++ {
		qq[i] = getNextInt(scanner)
	}

	ans := faci(qq) - faci(pp)
	if ans < 0 {
		ans = -ans
	}
	fmt.Fprintln(writer, ans)
}

func faci(p []int) int {
	n := len(p)
	fac := make([]int, n)
	fac[0] = 1
	fac[1] = 1
	for i := 2; i < n; i++ {
		fac[i] = fac[i-1] * i
	}
	ans := 0
	used := make([]bool, n)
	for i := 0; i < n; i++ {
		sum := 0
		for j := p[i] - 1; j >= 0; j-- {
			if used[j] {
				continue
			}
			sum++
		}
		used[p[i]-1] = true
		ans += sum * fac[n-1-i]
	}

	return ans
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    string S;
    cin >> S;
    int N = S.size();
    int K = N;
    rep(i, 0, N - 1)
    {
        if (S[i] != S[i + 1])
        {
            chmin(K, max(i + 1, N - i - 1));
        }
    }
    cout << K << endl;
}


Measured memory_bytes: 512
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		Scanner scn = new Scanner(System.in);
		String s = scn.next();
		String[] list = s.split("");
      	int add = 0;
      	for(int i=0; i<s.length(); ++i){
            if(list[i].equals("o")){
                add = add + 100;
            }
        }
      	System.out.println(700+add);
	}
}


Measured memory_bytes: 35668
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val sc = FastScanner(System.`in`)

    val h = sc.nextInt()
    val n = sc.nextInt()
    val a = Array(n) {sc.nextInt()}

    println(if(a.sum() >= h) "Yes" else "No")
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}





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

unsigned sumOfDigits(unsigned num){
  int sum=0;
  while(num > 0){
  	sum += num%10;
  	num = num/10;
  }
  return sum;
}
  
int main(){
  int n;
  cin>>n;
  int sum = sumOfDigits(n);
  if(n%sum == 0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}
  

Measured memory_bytes: 256
import numpy as np


N = int(input())
H = np.array(list(map(int, input().split())))

R = 0

for i in range(1, max(H)+1):
    FL = ''.join(['1' if h else '0' for h in (H >= i).tolist()]).split('0')
    while '' in FL:
        FL.remove('')
    R += len(FL)

print(R)


Measured memory_bytes: 12480
h,w = gets.split.map(&:to_i)
a = Array.new(h){ gets.chomp }

seen = Array.new(h){ Array.new(w){ false } }
DX = [ 0, 1, 0,-1, 1,-1, 1,-1]
DY = [ 1, 0,-1, 0, 1,-1,-1, 1]
inside = -> y, x { 0 <= y && y < h && 0 <= x && x < w }

bfs = -> sy,sx do
  return 0 if seen[sy][sx]
  que = [[sy,sx]]
  seen[sy][sx] = true
  black = 0
  white = 0
  while que.size > 0
    y,x = que.pop
    a[y][x] == "#" ? black += 1 : white += 1
    4.times do |i|
      ny = y + DY[i]
      nx = x + DX[i]
      next unless inside[ny,nx]
      next if seen[ny][nx]
      next if a[y][x] == a[ny][nx] # 同じ色なら対象外
      que << [ny,nx]
      seen[ny][nx] = true
    end
  end
  return black * white
end

ans = 0
h.times do |y|
  w.times do |x|
    ans += bfs[y,x]
  end
end
puts ans

Measured memory_bytes: 10876
A, B, C = [int(_) for _ in input().split()]
if [A - B, A - C] == [0, 0] and A % 2 == 0:
    print(-1)
    exit()
i = 0
while not any([A % 2, B % 2, C % 2]):
    A, B, C = (B + C) / 2, (C + A) / 2, (A + B) / 2
    i += 1
print(i)


Measured memory_bytes: 3060
N = int(input())
T,A = map(int,input().split())
H = map(int,input().split())
to = 100000000000
c = 1
for i in H:
    temp = T-i*0.006
    b = A-temp
    if b < 0:
        b = -b
    if to > b:
        to = b
        k = c
    c += 1
print(k)

Measured memory_bytes: 3060
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
int s[1<<10][1<<10];
int ans[1<<10][1<<10];
int h[1<<10][1<<10];
void solve(int n){
    if(n==0) return;
    solve(n-1);
    for(int i=0; i<(1<<(n-1)); i++){
        for(int j=0; j<(1<<(n-1)); j++) h[i^(1<<(n-1))][j]=h[i][j], h[i][j^(1<<(n-1))]=h[i][j], h[i^(1<<(n-1))][j^(1<<(n-1))]=(1^h[i][j]);
    }
}
int main()
{
    int n, m;
    cin>>n>>m;
    bool rev=0;
    if(n>m) rev=1, swap(n, m);
    solve(n);
    for(int i=0; i<(1<<n); i++){
        for(int j=0; j<(1<<n); j++){
            if(h[i][j]){
                for(int k=0; k<(1<<(m-n)); k++) s[i][(j<<(m-n))^k]=1;
            }
        }
    }
    for(int i=1; i<(1<<n); i++){
        for(int j=1; j<(1<<m); j++){
            ans[i][j]=s[i][j-1]^s[i-1][j]^s[i-1][j-1]^s[i][j];
        }
    }
    if(rev){
        for(int i=1; i<(1<<m); i++){
            for(int j=1; j<(1<<n); j++) cout<<ans[j][i];
            cout<<endl;
        }
    }else{
        for(int i=1; i<(1<<n); i++){
            for(int j=1; j<(1<<m); j++) cout<<ans[i][j];
            cout<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 13568
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=1,i;
    cin>>n;
    for(i=1;;i++){
    	sum=sum*2;
    	if(sum>n){
			cout<<sum/2;
			return 0;
		}
    	if(sum==n){
			cout<<sum;
			return 0;
		}
	}
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool conf[100005];
string s;
bool didIt;
int n;
 
void solve() {
    if (didIt) return;
    static int bla = 0;
    bla++;
    for (int i = 1; i < n - 2; i++) {
        if ((!conf[i] && s[i] == 'o') || (conf[i] && s[i] == 'x'))
            conf[i + 1] = conf[i - 1];
        else
            conf[i + 1] = !conf[i - 1];
    }
    int i = n - 2;
 
    if ((!conf[i] && s[i] == 'o') || (conf[i] && s[i] == 'x')){
        if (conf[i - 1] != conf[i + 1]) return;}
    else
        if (conf[i - 1] == conf[i + 1]) return;
 
    i = n - 1;
    if ((!conf[i] && s[i] == 'o') || (conf[i] && s[i] == 'x')) {
        if (conf[i - 1] != conf[0]) return;
    }
    else
        if (conf[i - 1] == conf[0]) return;
 
    didIt = true;
    for (int i = 0; i < n; i++) {
        if (conf[i]) cout << 'W';
        else cout << 'S';
    }
    cout << endl;
 
}
 
 
int main() {
    cin >> n;
    cin >> s;
    conf[0] = 0;
    if (s[0] == 'o') {
        conf[1] = 0;
        conf[n - 1] = 0;
        solve();
        conf[1] = 1;
        conf[n - 1] = 1;
        solve();
    }
    else {
        conf[1] = 0;
        conf[n - 1] = 1;
        solve();
        conf[1] = 1;
        conf[n - 1] = 0;
        solve();
    }
 
    conf[0] = 1;
 
    if (s[0] == 'x') {
        conf[1] = 0;
        conf[n - 1] = 0;
        solve();
        conf[1] = 1;
        conf[n - 1] = 1;
        solve();
    }
    else {
        conf[1] = 0;
        conf[n - 1] = 1;
        solve();
        conf[1] = 1;
        conf[n - 1] = 0;
        solve();
    }
 
    if (!didIt) cout << -1 << endl;
 
 
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cmath>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
    }

    sort(a.begin(), a.end());
    int flag = 0;
    for (int i = 0; i < n-1; i++) {
        if (a.at(i) == a.at(i+1)) {
            flag = 1;
            break;
        }
    }

    if (flag == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 1024
// atcoder 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    int N;
    cin >> N;
    if (N==1){
        cout << "Hello World" << endl;
        return 0;
    }
    else{
        int A, B;
        cin >> A >> B;
        cout << A+B << endl;
        return 0;
    }
}


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

#define endl "\n"

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

//REPEAT
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int 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,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//grobal variable
//------------------------------------------
int N,M;
VI Vec;

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

    int N; cin >> N;
    VI T(N), X(N), Y(N);
    REP(i, N) cin >>T.at(i) >> X.at(i) >> Y.at(i);

    int x_=0, y_=0, t_=0;

    bool can=true;
    REP(i, N)
    {
      if (abs(X.at(i) + Y.at(i) - T.at(i))%2 == 1)
      {
        can=false;
        break;
      }
      if (abs(X.at(i)-x_)+abs(Y.at(i)-y_) > T.at(i) - t_)
      {
        can=false;
        break;
      }
      x_=X.at(i);y_=Y.at(i);t_=T.at(i);

    }
    if (can) cout << "Yes" << endl;
    else cout << "No" << endl;


    return 0;
}


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

#ifdef LOCAL
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define dbgv(x) cerr << #x << " = " << x << endl
#define dbga(arr, len) {cerr << #arr << " = "; for (int _ = 0; _ < len; _++)\
cerr << arr[_] << " "; cerr << endl;}
#define dbgi(it) {cerr << #it << " = "; for (const auto& _ : it)\
cerr << _ << " "; cerr << endl;}
#else
#define dbg(...) (void)0
#define dbgv(x) (void)0
#define dbga(arr, len) (void)0
#define dbgi(it) (void)0
#endif

using ll = long long;
using dbl = long double;
using pii = pair<int, int>;

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

    for (int i = 1; i <= n; ++i) {
        int m = i * 108 / 100;
        if (m == n) {
            printf("%d\n", i);
            return;
        }
    }
    printf(":(\n");
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    solve();

    dbg("\n\ntime = %.3lf\n", (double)clock() / CLOCKS_PER_SEC);
}


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

using namespace std;

#define debug(x,y) cout<<(#x)<<" " <<(#y)<<" is " << (x) <<" "<< (y) << endl
#define watch(x) cout<<(#x)<<" is " << (x) << endl
#define fast ios_base::sync_with_stdio(false)
#define fie(i,a,b) for(i=a;i<b;i++)
#define MOD 1000000007
#define mod 998244353
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define ll long long
#define lld long long int
#define ALL(x) (x).begin(),(x).end()

typedef vector<lld> vi;
typedef vector<vector<lld>> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<pair<lld, lld>> vpi;
typedef long long LL;

lld dp[2001];

lld solve(lld n) {
	if (n == 0) return dp[n] = 1;
	if (n == 1 || n == 2) return dp[n] = 0;
	if (dp[n] != -1) return dp[n];
	lld c = 0;
	for (lld i = 3; i <= n; i++) {
		if (n - i >= 0) c += solve(n - i);
		c %= MOD;
	}
	return dp[n] = c;

}

int main() {
	fast;
	cin.tie(0);
	lld n;
	cin >> n;
	if (n == 1 || n == 2) cout << "0" << endl;
	else {
		memset(dp, -1, sizeof(dp));
		cout << solve(n) << endl;
	}
}








Measured memory_bytes: 3648
#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1'000'000'000ll + 7;
//const i64 smod = 998244353ll;
//const i64 inf = 1'000'000'000'000'000'000ll + 7;
//const i64 inf = 1'000'000'007;

const double inf = 1e12;

const long double eps = 1e-8;

i64 h, w, m;
vector<pair<i64, i64>> a;
set<pair<i64, i64>> z;

vector<set<i64>> rows;
vector<set<i64>> cols;

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed); cerr.precision(15); cerr.setf(ios::fixed);
    cin >> h >> w >> m;

    a = vector<pair<i64, i64>>(m);
    rows = vector<set<i64>>(h);
    cols = vector<set<i64>>(w);

    for (i64 i = 0; i < m; i++) {
        i64 x, y;
        cin >> x >> y;
        x -= 1;
        y -= 1;
        a[i] = { x, y };
        z.insert({ x, y });
    }

    for (i64 i = 0; i < m; i++) {
        rows[a[i].first].insert(a[i].second);
    }

    for (i64 i = 0; i < m; i++) {
        cols[a[i].second].insert(a[i].first);
    }

    i64 R = 0;
    for (i64 i = 0; i < m; i++) {
        i64 r = rows[a[i].first].size() + cols[a[i].second].size() - 1;
        R = max(R, r);
    }

    i64 mrow = 0;
    for (i64 i = 1; i < h; i++) {
        if (rows[mrow].size() < rows[i].size()) {
            mrow = i;
        }
    }

    i64 mcol = 0;
    for (i64 i = 1; i < w; i++) {
        if (cols[mcol].size() < cols[i].size()) {
            mcol = i;
        }
    }

    set<i64> mrows;
    for (i64 i = 0; i < h; i++) {
        if (rows[i].size() == rows[mrow].size()) {
            mrows.insert(i);
        }
    }

    set<i64> mcols;
    for (i64 i = 0; i < w; i++) {
        if (cols[i].size() == cols[mcol].size()) {
            mcols.insert(i);
        }
    }


    bool f = false;
    for (auto r : mrows) {
        if (f) {
            break;
        }
        for (auto c : mcols) {
            if (z.count(make_pair(r, c))) {
                continue;
            }
            R = max(R, (i64)(rows[mrow].size() + cols[mcol].size()));
            f = true;
            break;
        }
    }

    cout << R << endl;

    return 0;
}

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


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

  vector<int64_t> a(n);
  for(int i=0;i<n;i++){
    cin>>a.at(i);
  }

  //自分より前の最大と同じにする。
  int64_t sum=0;
  int64_t max_wk=0;
  for(int i=0;i<n;i++){
    max_wk=max(max_wk,a.at(i));

    if(a.at(i)<max_wk){
      sum+=max_wk-a.at(i);
    }
  }

  cout<<sum<<endl;

	return 0;
}



Measured memory_bytes: 4844
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define io ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define endl '\n'
#define mod 1000000007
#define inf 1000000000000000000
const double pi = acos(-1);
const int sz = 200002;
int n, m, q, k;
int main() {
	io
	cin>>n;
	vector<ll>a(n);
	map<ll, ll>freq;
	ll sum = 0;
	for(int i = 0; i<n; i++) {
		cin>>a[i];
		sum += a[i];
		freq[a[i]]++;
	}
	int q;
	cin>>q;
	for(int i = 0; i<q; i++) {
		ll b, c;
		cin>>b>>c;
		if(freq.count(b) == 0) {
			cout<<sum<<endl;
			continue;
		}
		sum -= freq[b]*b;
		freq[c] += freq[b];
		sum += freq[b]*c;
		freq.erase(b);
		cout<<sum<<endl;
	}
	
}


Measured memory_bytes: 7944
n,m=map(int,input().split())
x=list(map(int,input().split()))

x.sort()
dif=[]
for i in range(1,m):
    dif.append(x[i]-x[i-1])
dif.sort()

if n>=m:
    print(0)
else:
    print(sum(dif[:m-n]))

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

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e5+1e1;
const double eps=1e-10;

struct Node{
	int w2,w5,p;
};

Node a[MAXN<<1];
int b[3100][3100],n;
lint ans=0;

void Read(int id){
	int x=0,f=1,X=0,F=1,cnt=0;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	if(c=='.'){
		while(!isdigit(c)){	if(c=='-') F=-F;c=getchar();}
		while(isdigit(c)){X=(X<<3)+(X<<1)+(c-48);++cnt;c=getchar();}
	}
	lint k3=X*F;
	if(k3==0) cnt=0;
	while((k3) && (k3%10==0)) k3/=10,--cnt;
	lint k1=x*f;
	a[id].p=cnt;
	while(cnt--) k1*=10;
	lint k2=k1+k3;
	while((k2) && (k2%2==0)) ++a[id].w2,k2/=2;
	while((k2) && (k2%5==0)) ++a[id].w5,k2/=5;
	return;
}

int main(void){

	// freopen("testdata.in","r",stdin);
	// freopen("testdata.out","w",stdout);

	scanf("%d",&n);
	for(int i=1;i<=n;i++) Read(i);
	// for(int i=1;i<=n;i++) printf("%d %d %d\n",a[i].w2,a[i].w5,a[i].p);
	for(int i=1;i<=n;i++){
		lint res=0;
		int w2=a[i].w2,w5=a[i].w5,p=a[i].p;
		for(int j=0;j<=w2-p+48;j++) for(int k=0;k<=w5-p+48;k++) res+=b[j][k];
		++b[p-w2+48][p-w5+48];
		ans+=res;
		// printf("%lld ",res);
		// printf("%d %d\n",max(a[i].p-a[i].w2,0),max(a[i].p-a[i].w5,0));
	}
	printf("%lld\n",ans);

	return 0;
}

Measured memory_bytes: 6156
ff = [1, 1]
mod = int(1e9 + 7)

for i in xrange(2, 100002):
    abc = (  ff[i-1] * i ) % mod
    ff.append(abc)
    
#for i in xrange(1, 10):
#    print ff[i]
    
r = lambda : map(int, raw_input().split())

x, y = r()

n = min(x, y)
m = max(x, y)

if m-n > 1 :
    print 0
else :
    if m == n :
        print ( ff[m] * ff[n] * 2) % mod 
    else :
        print ( ff[m] * ff[n] ) % mod 


Measured memory_bytes: 5892
#include <iostream>
#include <string>
#include <vector>
using ll=long long;
using namespace std;

int main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=a*c;
    if(ans<b*c){
        ans=b*c;
    }
    if(ans<a*d){
        ans=a*d;
    }
    if(ans<b*d){
        ans=b*d;
    }
    cout<<ans<<endl;

    return 0;
}

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

using namespace std;

long long int fun(int n)
{
	if (n < 2)
		return 0;
	return (n * (n - 1)) / 2;
}
int main()
{
	char str[100];
	cin >> str;
	int len = strlen(str);
	for(int i=0;i<len/2;i++)
	{
		if(str[i]!=str[len-i-1])
		{
			cout << "No";
			return 0;
		}

	}

	int n=(len-1)/2;
	for(int i=0;i<n/2;i++)
	{
		if(str[i]!=str[n-i-1])
		{
			cout << "No";
			return 0;
		}
	}
	//	cout << "sdjksd";
    int p=(n+3)/2;
	for(int i=p;i<len;i++)
	{
		if(str[i]!=str[len-i-1])
		{
			cout << "No";
			return 0;
		}
	}
	//cout << "aksjdndks" << "\n";
	cout << "Yes";
	return 0;
}

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

int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int h,w,c;

int search_union(vector<int> panels){
  stack<int> s;
  int color=panels[0];
  vector<int> visited(h*w);
  int cnt=1;
  s.push(0);
  while(!s.empty()){
    int v=s.top();
    s.pop();
    int y=v/w,x=v%w;
    visited[y*w+x]=1;
    for(int i=0;i<4;++i){
      int ny=y+dy[i],nx=x+dx[i];
      if(0<=nx&&nx<w&&0<=ny&&ny<h&&panels[ny*w+nx]==color&&!visited[ny*w+nx]){
        s.push(ny*w+nx);
        visited[ny*w+nx]=1;
        cnt++;
      }
    }
  }
  return cnt;
}

vector<int> set_color(vector<int> panels,int target){
  stack<int> s;
  vector<int> new_panels=panels;
  s.push(0);
  vector<bool> visited(h*w);
  int color=panels[0];
  while(!s.empty()){
    int v=s.top();
    s.pop();
    int y=v/w,x=v%w;
    //cout<<"set "<<y<<" "<<x<<endl;
    visited[y*w+x]=1;
    new_panels[y*w+x]=target;
    for(int i=0;i<4;++i){
      int ny=y+dy[i],nx=x+dx[i];
      if(0<=nx&&nx<w&&0<=ny&&ny<h&&panels[ny*w+nx]==color&&!visited[ny*w+nx]){
        s.push(ny*w+nx);
      }
    }
  }
  return new_panels;
}

void print_vector(vector<int> panels){
  for(int i=0;i<h;++i){
    for(int j=0;j<w;++j){
      cout<<panels[i*w+j]<<" ";
    }
    cout<<endl;
  }
  cout<<endl;
}

int search(int rest,vector<int> panels){
  int mx=0;
  if(rest==0){
    //cout<<search_union(panels)<<endl;
    //print_vector(panels);
    return search_union(panels);
  }else if(rest==1){
    return search(rest-1,set_color(panels,c));
  }else{
    for(int i=1;i<=6;++i){
      if(i!=panels[0])mx=max(mx,search(rest-1,set_color(panels,i)));
    }
  }
  return mx;
}

int main(){
  cin>>h>>w>>c;
  while(h!=0){
    vector<int> panels(h*w);
    for(int i=0;i<h;++i){
      for(int j=0;j<w;++j){
        cin>>panels[i*w+j];
      }
    }
    cout<<search(5,panels)<<endl;
    cin>>h>>w>>c;
  }
  return 0;
}



Measured memory_bytes: 3072
#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()
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
	string S;
	cin >> S;
    string ans = S.substr(0, int(S.size())-8);

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


Measured memory_bytes: 256
#nに行くまでの道で正の閉路があればいくらでも大きくすることができる
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=map(int,input().split())
  es.append((a-1,b-1,c))

def BellmanFord(n,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n:
      #負の経路がある場合
      #さらにこっからn回繰り返してd[n-1]が更新されるかみる
      negative=[False]*n
      for i in range(n):
        for p,q,r in es:
          if d[q]<d[p]+r:
            negative[q]=True
            d[q]=d[p]+r
      if negative[n-1]==True:
        print("inf")
        exit()
      else:
        print(d[n-1])
        exit()
        
  print(d[n-1])
  
  
  
BellmanFord(n,0,es)

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

int main(){
    int N;
    cin >> N;
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec.at(i);
    }
    bool flag = 1;
    int count = 0;
    //flagでバブルソート 
    for (int i = 0; flag; i++) {
        flag = 0;
        for (int j = N-1; j >= i+1; j--) {
            if (vec.at(j) < vec.at(j-1)) {
                swap (vec.at(j), vec.at(j-1));
                flag = 1;
                count++;
            }
        }
    }
    for (int i = 0; i < N-1; i++) {
        cout << vec.at(i) << " ";
    }
    cout << vec.at(N-1) << endl;
    cout << count << endl;
}


Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
ll p=pow(10,9)+7;
ll phi(ll n) {
    ll result = n;
    for (ll i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            while(n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if(n > 1)
        result -= result / n;
    return result;
}
ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;      
    x = x % p;  
   while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p; 
    } 
    return res; 
} 

ll modInverse(ll n, ll p) 
{ 
    return power(n, p-2, p); 
}


 
int main() {
 
    ll n,k,i,j;
    cin>>n>>k;
    ll arr[n];
    for(i=0;i<n;i++)
    cin>>arr[i];
    ll dp[n][k+1];
    dp[0][0]=1;
    for(j=1;j<=k;j++)
    {
        if(j<=arr[0])
        dp[0][j]=1+dp[0][j-1];
        else
        dp[0][j]=dp[0][j-1];
        dp[0][j]%=p;
    }
    for(i=1;i<n;i++)
    {
        for(j=0;j<=k;j++)
        {
            if(j==0)
            dp[i][j]=1;
            else
            {
                if(j<=arr[i])
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
                else
                dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-arr[i]-1]+p;
            }
            dp[i][j]%=p;
        }
    }
    if(k>=1)
    cout<<(dp[n-1][k]-dp[n-1][k-1]+p)%p;
    else
    cout<<dp[n-1][0];
 
    return 0;
    
}  



Measured memory_bytes: 78336
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[1500];
    int i,n;
    cin>>s;
    n=strlen(s);
    if(n==2){
        cout<<s;
    }
    else{
        for(i=n-1;i>=0;i--){
            cout<<s[i];
        }
    }
return 0;


    }



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

int main(){
    int a, b;
    cin >> a >> b;
    string A, B;
    string astr = to_string(a);
    string bstr = to_string(b);
    if (a<b)
    {
        for (int i = 0; i < b; i++)
        {
            A = A + astr;
        }
        cout << A;
    }else
    {
        for (int i = 0; i < a; i++)
        {
            B = B + bstr;
        }
        cout << B;
    }
}

Measured memory_bytes: 256
/*input
100000 1
1 100000 100
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back

#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int raise(int a,int n,int m = MOD){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}

int ceil1(int n,int k){
    return floor1(n+k-1,k);
}

const int N = 1e5+2;
vector<int> adj[N];
bool vis[N];
int ans = 0;
int n,m;

void dfs(int u){
	if(vis[u])return;
	vis[u] = 1;
	for(int v:adj[u])dfs(v);
}


void solve(){
  	cin >> n >> m;
  	RE(i,m){
  		int x,y,z;cin >>x >> y >> z;
  		adj[x].pb(y);
  		adj[y].pb(x);
  	}
  	RE(i,n){
  		if(!vis[i]){
  			ans++;
  			dfs(i);
  		}
  	}
  	cout << ans;
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

Measured memory_bytes: 8960
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX_SUM 100000
vector<vector<ll>> dp(101, vector<ll>(100005, INT_MAX)), input;
  

int main()
{
    int n, a, b, w;
    long long int ans;
    cin >> n>>w;
    input.push_back({-1,-1});
    for(int i=0;i<n;i++)
    {
        cin >> a >> b;
        input.push_back({a, b});
    }
    dp[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=MAX_SUM;j++){
            if(j<input[i][1]){dp[i][j] = dp[i-1][j];}
            else{
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-input[i][1]]+input[i][0]);
            }
        }
    }
    for(int i=MAX_SUM;i>=0;i--){
        if(dp[n][i]<=w){cout<<i;return 0;}
    }

    return(0);
}

Measured memory_bytes: 80256
#include <stdio.h>
#include <math.h>

typedef struct {
	long double key;
	int id;
} data;

void merge_sort(data x[], int n)
{
	static data y[101] = {};
	if (n <= 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p].key < x[q].key)? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N, x[101], y[101];
	const long double pi = atanl(1.0) * 4.0;
	data d[101];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%d %d", &(x[i]), &(y[i]));
		if (x[i] == 0) d[i-1].key = (y[i] >= 0)? pi / 2.0: -pi / 2.0;
		else d[i-1].key = (x[i] > 0)? atanl((long double)y[i] / x[i]): atanl((long double)y[i] / x[i]) + pi;
		d[i-1].id = i;
	}
	merge_sort(d, N);
	
	int j, k;
	long double ans = 0.0, tmp;
	for (i = 0; i < N; i++) {
		x[0] = x[d[i].id];
		y[0] = y[d[i].id];
		tmp = sqrtl((long double)x[0] * x[0] + (long double)y[0] * y[0]);
		if (tmp > ans) ans = tmp;
		for (j = 1; j < N; j++) {
			x[0] += x[d[(i+j)%N].id];
			y[0] += y[d[(i+j)%N].id];
			tmp = sqrtl((long double)x[0] * x[0] + (long double)y[0] * y[0]);
			if (tmp > ans) ans = tmp;
		}
	}
	printf("%.10Lf\n", ans);
	fflush(stdout);
	return 0;
}

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

using namespace std;

int main(int argc, char const *argv[]) {
	
	int a, b, ans;
	cin >> a >> b;

	if(a <= 0 && b >= 0) {
		ans = 0;
	}
	else if(b < 0) {
		if((b-a+1)&1) ans = -1;
		else ans = 1;
	}
	else {
		ans = 1;
	}

	if(ans == 0) {
		printf("Zero\n");
	}
	else if(ans == 1) {
		printf("Positive\n");
	}
	else printf("Negative\n");
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    if (A >= 13) {
      System.out.println(B);
    } else if(A >= 6 && A <= 12) {
      System.out.println(B/2);
    } else {
      System.out.println(0);
    }
  }
}

Measured memory_bytes: 20820
#include<bits/stdc++.h>
using namespace std;
int main(){
  
  int N,M;
  cin>>N>>M;
  
  vector<int> A(M);
  int sum=0;
    for(int i=0;i<M;i++){
      cin>>A.at(i);
    sum += A.at(i);
    }
  if(N-sum>=0){
    cout << N-sum <<endl;
  }
  else {
    cout << "-1" <<endl;
  }
  
  
  return 0;
}

  
  


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

typedef long long ll;

static const int MAX = 1100;
static const int INFTY = (1 << 30);

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

// ワーシャルフロイド（全点対間最短経路）
void floyd() {
	for (int k = 0; k<n; k++) {
		for (int i = 0; i<n; i++) {
			if (d[i][k] == INFTY) continue;
			for (int j = 0; j<n; j++) {
				if (d[k][j] == INFTY) continue;
				// 頂点 k を経由する場合としない場合の最小コストを求める
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

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

	for (int i = 0; i<n; i++) {
		for (int j = 0; j<n; j++) {
			d[i][j] = ((i == j) ? 0 : INFTY);
		}
	}

	for (int i = 0; i<m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--; b[i]--;
	}
	for (int i = 0; i < m; i++) {
		d[a[i]][b[i]] = min(d[a[i]][b[i]], c[i]);
		d[b[i]][a[i]] = min(d[b[i]][a[i]], c[i]);
	}

	floyd();

	int ans=m;
	for (int i = 0; i < m; i++) {
		bool include=false;
		for (int j = 0; j < n; j++) {
			if(d[j][a[i]]+c[i] == d[j][b[i]]) include=true;
		}
		if(include) ans--;
	}

	cout << ans << endl;

}


Measured memory_bytes: 640
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC
{
    class ProgramC
    {
        static void Main(string[] args)
        {
            var n = long.Parse(Console.ReadLine());
            for (var i = 1; i <= n; i++)
            {
                Console.WriteLine(F(i));
            }
        }

        static int F(int n)
        {
            var result = 0;
            var end = Math.Sqrt(n);
            // Console.WriteLine(string.Format("n: {0}, end: {1}", n, end));

            for (var i = 1; i < end; i++)
            {
                for (var j = 1; j < end; j++)
                {
                    for (var k = 1; k < end; k++)
                    {
                        var r = i * i + j * j + k * k + i * j + i * k + j * k;

                        if (r == n)
                        {
                            result++;
                        }
                        if (r >= n)
                        {
                            break;
                        }
                    }
                }
            }
            return result;
        }
    }
}


Measured memory_bytes: 27644
//   ┏━━┓┏━━┓┏┓┏┓┏┳━┳┓┏━━┓┏━┳┓┏━━┓     ┏┳┓┏┳┓┏━┳━┓┏━━┓┏━┓
//   ┃┏┓┃┃━━┫┃┗┛┃┃┃┃┃┃┃┏┓┃┃┃┃┃┗┃┃┛     ┃┏┛┃┃┃┃┃┃┃┃┃┏┓┃┃╋┃
//   ┃┣┫┃┣━━┃┃┏┓┃┃┃┃┃┃┃┣┫┃┃┃┃┃┏┃┃┓     ┃┗┓┃┃┃┃┃┃┃┃┃┣┫┃┃┓┫
//   ┗┛┗┛┗━━┛┗┛┗┛┗━┻━┛┗┛┗┛┗┻━┛┗━━┛     ┗┻┛┗━┛┗┻━┻┛┗┛┗┛┗┻┛
#include<bits/stdc++.h>
using namespace std;
#define FOR(a, c) for (int a  = 0; a<c ; a++)
#define FORL(a, b, c) for (int a  = b;  a< c ; a++)
typedef long long int ll;
int main()
{
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  //ll ans = INT_MIN;
  // if(b>0 && d>0){
  //   cout<< b*d;
  // }
  // else if(b>0 && d<0){
  //   cout<< a*d;
  // }
  // else if(b<0 && d>0){
  //   cout<< b*c;
  // }
  // else if(b==0 && d>0){
  //   cout<< 0;
  // }
  // else if(d==0 && b>0){
  //   cout<< 0;
  // }
  // else if(b==0 && d<0){
  //   cout<< 0;
  // }
  // else if(d==0 && b<0){
  //   cout<< 0;
  // }
  // else{
  //   cout<< a*c;
  // }
  ll temp=0;
  cout<< max(max(b*d, a*d), max(a*c, b*c));
  return 0;
}
// By Ashwani Kumar, Indian Institute Of Technology(IIT), Guwahati.
//   ╔══╗╔══╗╔══╗     ╔══╗╔╦╗╔╦═╦╗╔══╗╔╗╔╗╔══╗╔══╗╔══╗
//   ╚║║╝╚║║╝╚╗╔╝     ║╔═╣║║║║║║║║║╔╗║║╚╝║║╔╗║╚╗╔╝╚║║╝
//   ╔║║╗╔║║╗─║║─     ║╚╗║║║║║║║║║║╠╣║║╔╗║║╠╣║─║║─╔║║╗
//   ╚══╝╚══╝─╚╝─     ╚══╝╚═╝╚═╩═╝╚╝╚╝╚╝╚╝╚╝╚╝─╚╝─╚══╝


Measured memory_bytes: 3644
x = int(input())
s = list(input())

while True:
    check = 0
    for i in range(len(s)):
        if s[i] == "(":
            check += 1
        else:
            check -= 1
            
        if check < 0:
            s.insert(0, "(")
            break
    else:
        for _ in range(check):
            s.append(")")
        print("".join(s))
        break

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<list>
#include <array>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define INF I64_MAX
#define MOD 1000000007



void solve(void)
{ 
  int N;
  cin>>N;
  vector<int> vec(N,0);
  for (int i = 0; i < N; i++)
  {
    cin>>vec[i];
  }

  int count = 0;

  for (int i = 0; i < N; i++)
  {
    if(count + 1 == vec[i])count++;
  }
  if(count == 0) count = vec.size() + 1;

  cout<<(int)(vec.size()) - count <<endl;
  
  
  
  
  return;  
}



int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  // std::cout << std::fixed;
  // std::cout << std::setprecision(8);

  solve();

 
  return 0;
}

Measured memory_bytes: 1792
N,T=map(int,input().split())
import numpy as np
dp=np.zeros(T,dtype=int)
maxval=0

meals=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  meals[i]=a,b

meals=sorted(meals,key=lambda x:x[0])

for i in range(N):
  a,b=meals[i]
  if maxval<dp[-1]+b:
    maxval=dp[-1]+b
  np.maximum(dp[:-a]+b,dp[a:],out=dp[a:])
  
print(maxval)

Measured memory_bytes: 12520
N = int(input())
B = list(map(int, input().split(" ")))

l = []
for i in range(N-1, -1, -1):
    for j in range(len(B)-1, -1, -1):
        if B[j] == j+1:
            l.append(j+1)
            B.pop(j)
            break

if len(B) == 0:
    for l_i in l[::-1]:
        print(l_i)
else:
    print(-1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i = x; i < (int)(n); i++)
#define rep_ll(i,x,n) for(ll i = x; i < (ll)(n); i++)
using namespace std;
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
const long double PI = (acos(-1));
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1};
ll mod = 1000000007;
int main(){
    const int MAX_SIZE=1000005;
    bool num[MAX_SIZE];
    rep(i, 0, MAX_SIZE) num[i]=false;
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    sort(a.begin(), a.end());
    int cnt=0;
    //エラトステネスの篩
    rep(i, 0, n){
        if(num[a[i]]==true) continue;
        //重複判定、昇順なのでこれでOK
        if(!(i<n-1&&a[i]==a[i+1])) cnt++;

        for(int j = a[i]; j < MAX_SIZE; j+=a[i]) num[j]=true;
    }
    cout << cnt;

    return 0;
}

Measured memory_bytes: 4984