akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(unsigned x){
  int s=0;
  char f[10];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(unsigned long long x){
  int s=0;
  char f[21];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(double x){
  printf("%.15f",x);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
inline void wt_L(string &x){
  int i=0;
  for(i=0;x[i]!='\0';i++){
    putchar_unlocked(x[i]);
  }
}
int N;
int A;
int dp[200001];
int main(){
  int Lj4PdHRW;
  rd(N);
  for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
    rd(A);
    dp[A] = dp[A-1] + 1;
  }
  {
    int e98WHCEY;
    int cTE1_r3A;
    if(N+1==0){
      cTE1_r3A = 0;
    }
    else{
      cTE1_r3A = dp[0];
      for(e98WHCEY=(1);e98WHCEY<(N+1);e98WHCEY++){
        cTE1_r3A = max_L(cTE1_r3A, dp[e98WHCEY]);
      }
    }
    wt_L(N -cTE1_r3A);
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20191125-1

// --- original code ---
// int N, A, dp[200001];
// {
//   rd(N);
//   rep(N){
//     rd(A);
//     dp[A] = dp[A-1] + 1;
//   }
//   wt(N - max(dp(N+1)));
// }


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

using namespace std;

void test_case()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=0;i<n;i++){
        int temp;scanf("%d",&temp);
        m-=temp;
    }
    printf("%d\n",max(-1,m));
}

int main()
{
        test_case();

    return 0;
}


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

int main(void)
{
    double a,b,x,th;
    scanf("%lf %lf %lf", &a, &b, &x);
    if(a*a*b<=2*x) {
        th = atan(2*(b/a-x/a/a/a));
    } else {
        th = atan(a*b*b/2/x);
    }
    printf("%.10lf\n", th/asin(1)*90);
    return 0;
}



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

int main(){
int n; cin >> n;
string s; cin >> s; 
int ans=1;
rep(i,n-1){
if(s[i] != s[i+1]) ans+=1;
}
cout << ans << endl;
return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#pragma gcc optimize("ofast")
using namespace std;

#define ll long long //data types used often, but you don't want to type them time by time
#define ull unsigned long long
#define ui unsigned int
#define mod 1000000007
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0); //to synchronize the input of cin and scanf
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;


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

    vector<double>p(n+1);
    rep(i,1,n+1)cin>>p[i];

    vector<vector<double>>dp(n+1,vector<double>(n+1,0.0));
    dp[0][0] = 1.0;

    rep(i,1,n+1)
    {
        rep(j,0,i+1)
        {
            if(j==0)dp[i][j] = dp[i-1][j]*(1.0-p[i]);
            else dp[i][j] = dp[i-1][j]*(1.0-p[i])+dp[i-1][j-1]*p[i];
        }
    }
    double ans = 0.0;
    for(ll i=n/2+1;i<=n;i++)ans+=dp[n][i];
    cout<<fixed<<setprecision(10)<<ans<<endl;
    return 0;
}


Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

const ll INF = 1LL<<50;

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

    vector<ll> a(M), b(M), c(M);
    for(int i=0; i<M; i++){
        cin >> a[i] >> b[i] >> c[i];
        c[i] = -c[i];
    }

    vector<ll> dist(N+1, INF);
    dist[1] = 0;

    for(int loop=0; loop<N; loop++){
        for(int j=0; j<M; j++){

            if(dist[a[j]] == INF) continue;
            
            if(dist[a[j]] + c[j] < dist[b[j]]){
                dist[b[j]] = dist[a[j]] + c[j];
            }
        }
    }

    ll ans = dist[N];

    vector<bool> negative(N+1, false);

    for(int loop=0; loop<N; loop++){
        for(int i=0; i<M; i++){
            if(dist[a[i]] == INF) continue;

            if(dist[a[i]] + c[i] < dist[b[i]]){
                dist[b[i]] = dist[a[i]] + c[i];
                negative[b[i]] = true;
            }

            if(negative[a[i]] == true){
                negative[b[i]] = true;
            }
        }
    }

    if(negative[N]) cout << "inf" << endl;
    else cout << -ans << endl;
}

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

    #define ll long long
    #define ld long double
    #define pb push_back
    #define mod 1000000007
    #define mk make_pair


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

      ll n,i,a;
      ld ans=0;
      cin>>n;
      for(i=0;i<n;i++){
        cin>>a;
        ans+=(1.0/a);
      }
      cout<< 1.0 / ans ;

      return 0;
      
      }

Measured memory_bytes: 256
n,t=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(n):
  if i==0:
    ans+=t
  elif a[i-1]+t<=a[i]:
    ans+=t
  else:
    ans+=a[i]-a[i-1]
print(ans)

Measured memory_bytes: 30836
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,sum=0,m,q=0;
    cin>>n;
    int t[n+2];
    for(i=0;i<n;i++)
        {
            cin>>t[i];
            q+=t[i];
        }
    cin>>m;
    int p[m+2],x[m+2];
    for(i=0;i<m;i++)
    {
        sum=q;
        cin>>p[i]>>x[i];
        sum=sum-t[p[i]-1]+x[i];
        cout<<sum<<"\n";
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <string>
#include <cstring>
#include <cctype>
#include <numeric>
#include <cstdio>
#include <math.h>
#include <functional>
using namespace std;
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vs = vector<string>;
using vl = vector<ll>;
using vvl = vector<vl>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using f80 = __float80;
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (i64 i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define RS(x) rsort(x.begin(),x,end()))
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
#define fst first
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define sw swap
#define UP(x) transform(x.begin(), x.end(), x.begin(), ::toupper);
#define LOW(x) transform(x.begin(), x.end(), x.begin(), ::tolower);
#define na(a, n) rep(i, n) cin >> a[i];
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
vb d(10);
int ans(int x)
{
    while (x)
    {
        if (d[x % 10])
            return 0;
        x /= 10;
    }
    return 1;
}
//ここからメイン
int main()
{
 ll a;
  cin >> a;
  cout <<"ABC"<< a;
    }

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <bitset>

int main(int argc, char* argv[])
{
  std::bitset<10> flg;
  for (int i = 0; i < 4; ++i) {
    std::string s;
    std::cin >> s;
    const auto v = s[0] - '0';
    flg[v] = !flg[v];
  }

  if (flg[1] && flg[9] && flg[7] && flg[4]) std::cout << "YES";
  else std::cout << "NO";

  return 0;
}

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

const int INF = 999999999;
int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    vector<int> vW(N+1, 0), vE(N+1, 0);
    for(int i=0; i<N; i++){
        vW[i+1] += vW[i];
        if(S[i] == 'W') vW[i+1]++;
        vE[i+1] += vE[i];
        if(S[i] == 'E') vE[i+1]++;
    }
    // 大きな値で初期化しておく
    int ans = INF;
    for(int i=0; i<N; i++){
        int now = vW[i] + (vE[N]-vE[i+1]);
        if(ans > now) ans = now;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3076
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
    n: usize,
    mut l:[usize; n]
    }
    l.sort();
    let mut ans = 0;
    for i in 0..n {
        for j in i + 1..n {
            let (mut s, mut t) = (0, i);
            while s < t {
                let mid = (s + t) / 2;
                if l[j] < l[i] + l[mid] {
                    t = mid;
                } else {
                    s = mid + 1;
                }
            }
            ans += i - s
        }
    }
    println!("{}", ans);
}



Measured memory_bytes: 2208
n = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)
l = Array.new(n+2, 0)
r = Array.new(n+2, 0)
l[0] = 0
1.upto(n) do |i|
  l[i+1] = (l[i]).gcd(a[i-1])
end

r[n+1] = 0
(n).downto(0) do |i|
  r[i] = (r[i+1]).gcd(a[i-1])
end

ans = 0
1.upto(n) do |i|
  ans = [ans, (l[i]).gcd(r[i+1])].max
end
puts ans


Measured memory_bytes: 13836
#include <bits/stdc++.h>
#define loop(n, i) for(int i=0;i<n;i++)
#define loop1(n, i) for(int i=1;i<=n;i++)
#define rloop(n, i) for(int i=n;i;i++)
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;

int main() {
    int n, x; cin >> n >> x;
    V<int> L(n);
    loop (n, i) cin >> L[i];

    int ans = 1;
    int p = 0;
    loop (n, i) {
        p += L[i];
        if (p <= x) ans++;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int> l(n);
    for (int i = 0; i < n; ++i) {
        cin >> l[i];
    }
    sort(l.begin(), l.end());
    ll ans = 0;
    for (int a = 0; a < n; ++a) {
        for (int b = a + 1; b < n; ++b) {
            auto it_r = lower_bound(l.begin(), l.end(), l[a] + l[b]);
            auto it_l = upper_bound(l.begin(), l.end(), max(l[b] - l[a], l[a] - l[b]));
            ans += it_r - it_l;

            int idx_l = it_l - l.begin();
            int idx_r = it_r - l.begin();
            if (idx_l <= a && a <= idx_r)
                --ans;
            if (idx_l <= b && b <= idx_r)
                --ans;
        }
    }
    cout << ans / 3 << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] In = Console.ReadLine().Split(' ');
            int n = int.Parse(In[0]);
            int k = int.Parse(In[1]);
            int q = int.Parse(In[2]);
            var P = new int[n + 1];
            P = Enumerable.Repeat(k-q, n + 1).ToArray();
            for(int i=0; i < q; i++)
            {
                int a = int.Parse(Console.ReadLine());
                P[a]++;
            }
            for(int i = 1; i < n + 1; i++)
            {
                if (P[i] > 0) Console.WriteLine("Yes");
                else Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 31824
from sys import setrecursionlimit, stdin


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


readline = stdin.readline
setrecursionlimit(10 ** 6)

N, Q = map(int, readline().split())

parent = [-1] * (N + 1)
result = []
for _ in range(Q):
    t, u, v = map(int, readline().split())
    if t == 0:
        unite(parent, u, v)
    elif t == 1:
        if find(parent, u) == find(parent, v):
            result.append(1)
        else:
            result.append(0)

print(*result, sep='\n')


Measured memory_bytes: 13548
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <iomanip>

using namespace std;

int main(){
    int a, b, c; cin >> a >> b >> c;
    cout << (a+b>=c ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
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;
}
const long long INF = 1LL << 60;

int main()
{
    int a, b;
    cin >> a >> b;
    int let = 1, ans = 0;

    while (let < b)
    {
        --let;
        let += a;
        ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3584
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        
        int A1= scan.nextInt();
        int A2 = scan.nextInt();
        int A3 = scan.nextInt();
        
        if (A1 + A2 + A3 < 22) {
            System.out.println("win");
        }
        
        else {
           System.out.println("bust");
        } 
    }
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5050;
int d[N];
int main()
{
    int k, q;
    cin >> k >> q;
    for (int i = 0; i < k; ++i)
        cin >> d[i];
    while (q--) {
        ll n, x, m;
        cin >> n >> x >> m;
        x %= m;
        --n;
        ll y = x, s = 0, ans = 0;
        for (int i = 0; i < k; ++i) {
            int t = d[i] % m;
            y += (i < n % k) * t;
            s += t;
            if (!t) {
                ans += n / k + (i < n % k);
            }
        }
        y += n / k * s;
        ans += y / m - x / m;
        cout << n - ans << '\n';
    }
}


Measured memory_bytes: 384
#include <iostream>

void call(int n);

int main()
{
	int n;
	std::cin >> n;
	call(n);
	return 0;
}

void call(int n)
{
	int i = 1;
	while (i <= n) 
	{
		int x = i;
		if (x % 3 == 0)
		{
			std::cout << " " << i;
		}
		else
		{
			do {
				if (x % 10 == 3)
				{
					std::cout << " " << i;
					break;
				}
				x /= 10;
			} while (x != 0);
		}
		i++;
	}
	std::cout << '\n';
}

Measured memory_bytes: 3108
#include<stdio.h>
main()
{

  int x, y, n, s,cnt = 0,count;
  int a[1000000] = {0};

  for(x = 2;x < 1000000;x++){
    for(y = x + x;y < 1000000;y += x){
      a[y] = 1;
    }
  }



  while(1){
    scanf("%d", &n);
    if(n==0)
      break;
    count=0;
    x=2;
    s=0;
    while(count<n){
      if(a[x]==0){
	s+=x;
	count++;
      }
      x++;
    }
  

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

Measured memory_bytes: 4316
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF=99999999999999;
const ll MOD=1000000007;
 
int main() {
  ll n;
  cin >> n;
  cout << (n*(n-1))/2;
  
 return 0;
}


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

using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

vector<vector<ll> > mult(vector<vector<ll> > a, vector<vector<ll> > b) {
    if(a.size() == 0) return {};
    if(a[0].size() == 0) return {};
    if(b.size() == 0) return {};
    if(b[0].size() == 0) return {};
    if(a[0].size() != b.size()) return {};
    int resultRow = a.size(), resultCol = b[0].size(), n = a[0].size();
    vector<vector<ll> > product(resultRow, vector<ll>(resultCol));
    for(int i = 0; i < resultRow; ++i) {
        for(int j = 0; j < resultCol; ++j) {
            product[i][j] = 0;
            for(int k = 0; k < n; ++k) {
                product[i][j] += a[i][k] * b[k][j];
                product[i][j] %= mod;
            }
        }
    }
    return product;
}

vector<vector<ll> > power(vector<vector<ll> > matrix, ll b) {
    if (b <= 1) return matrix;
    vector<vector<ll> > temp = power(matrix, b/2);
    if (b % 2 == 0) return mult(temp, temp);
    return mult(mult(temp, temp), matrix);
}

int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> v(n,vector<ll>(n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> v[i][j];
        }
    }

    v = power(v,m);

    ll total = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            total += v[i][j];
            total %= mod;
        }
    }

    cout << total << endl;
}


Measured memory_bytes: 1664
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <utility>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <climits>
#include <numeric>
#include<stdio.h>
#include <queue>
#include <iomanip>
#include <float.h>
#include <set>
#include<functional>
#include <stack>
#include <time.h>
#include <climits>
#include <bitset>
using namespace std;
int  gcd(int a, int b) {
	if (a < b) gcd(b, a);
	int r;
	while ((r = a%b)) {
		a = b;
		b = r;
	}
	return b;
}
long long lcm(long long a, long long b) {
	return a / gcd(a, b) * b;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

long long modinv(long long a, long long mod) {
	long long b = mod, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t*b; swap(a, b);
		u -= t*v; swap(u, v);
	}
	u %= mod;
	if (u < 0) u += mod;
	return u;
}
namespace NTT {
	const int MOD = 998244353;  // to be set appropriately
	const long long PR = 3;     // to be set appropriately

	void trans(vector<long long> &v, bool inv = false) {
		int n = (int)v.size();
		for (int i = 0, j = 1; j < n - 1; j++) {
			for (int k = n >> 1; k >(i ^= k); k >>= 1);
			if (i > j) swap(v[i], v[j]);
		}
		for (int t = 2; t <= n; t <<= 1) {
			long long bw = modpow(PR, (MOD - 1) / t, MOD);
			if (inv) bw = modinv(bw, MOD);
			for (int i = 0; i < n; i += t) {
				long long w = 1;
				for (int j = 0; j < t / 2; ++j) {
					int j1 = i + j, j2 = i + j + t / 2;
					long long c1 = v[j1], c2 = v[j2] * w % MOD;
					v[j1] = c1 + c2;
					v[j2] = c1 - c2 + MOD;
					while (v[j1] >= MOD) v[j1] -= MOD;
					while (v[j2] >= MOD) v[j2] -= MOD;
					w = w * bw % MOD;
				}
			}
		}
		if (inv) {
			long long inv_n = modinv(n, MOD);
			for (int i = 0; i < n; ++i) v[i] = v[i] * inv_n % MOD;
		}
	}

	// C is A*B
	vector<long long> mult(vector<long long> A, vector<long long> B) {
		int size_a = 1; while (size_a < A.size()) size_a <<= 1;
		int size_b = 1; while (size_b < B.size()) size_b <<= 1;
		int size_fft = max(size_a, size_b) << 1;

		vector<long long> cA(size_fft, 0), cB(size_fft, 0), cC(size_fft, 0);
		for (int i = 0; i < A.size(); ++i) cA[i] = A[i];
		for (int i = 0; i < B.size(); ++i) cB[i] = B[i];

		trans(cA); trans(cB);
		for (int i = 0; i < size_fft; ++i) cC[i] = cA[i] * cB[i] % MOD;
		trans(cC, true);

		vector<long long> res((int)A.size() + (int)B.size() - 1);
		for (int i = 0; i < res.size(); ++i) res[i] = cC[i];
		return res;
	}
};

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	long long x, y;
	cin >> x >> y;
	if (abs(x - y) > 1)cout << "Alice";
	else cout << "Brown";
}

Measured memory_bytes: 384
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
//ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	ll n,q ;
	cin >> n >> q ;
	vector<tuple<ll,ll,ll>> block(n) ;
	for(int i=0;i<n;i++){
		ll s,t,x ;
		cin >> s >> t >> x ;
		t-- ;
		get<0>(block.at(i)) = x ;
		get<1>(block.at(i)) = s ;
		get<2>(block.at(i)) = t ;
	}
	sort(block.begin(),block.end()) ;
	vll d(q,0) ;
	for(int i=0;i<q;i++){
		ll sub ; cin >> sub ;
		d.at(i) -= sub ;
	}
	vll ans(q,-1) ;
	vll pass(q,-1) ;
//	cout << endl ;
	for(int i=0;i<n;i++){
		if(get<0>(block.at(i))-get<1>(block.at(i))<d.at(q-1)) continue ;
		if(get<0>(block.at(i))-get<2>(block.at(i))>d.at(0)) continue ;
		ll l,r,m ;
		ll right,left ;
		ll check = get<0>(block.at(i))-get<1>(block.at(i)) ;
		if(check>=d.at(0)){
			right = 0 ;
		}else{
			l = q-1 ;
			r = 0 ;
			while(l>r+1){
				m = (l+r)/2 ;
				if(d.at(m)>check) r = m ;
				else l = m ;
			}
			right = l ;
		}
		check = get<0>(block.at(i))-get<2>(block.at(i)) ;
		l = q-1 ;
		r = 0 ;
		if(check<=d.at(q-1)){
			left = q-1 ;
		}else{
			while(l>r+1){
				m = (l+r)/2 ;
				if(d.at(m)<check) l = m ;
				else r = m ;
			}
			left = r ;
		}
//		cout << left << " " << right << " " << get<0>(block.at(i)) << endl ;
		for(int j=right;j<=left;j++){
//			cout << j << " " ;
			if(pass.at(j)==-1){
				ans.at(j) = get<0>(block.at(i)) ;
				pass.at(j) = left ;
			}else{
				j = pass.at(j) ;
			}
		}
//		cout << endl ;
	}
	for(int i=0;i<q;i++){
		cout << ans.at(i) << endl ;
	}
}


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

#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef vector<int> vi;

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

	vi v(n);
	vi c(n);
	rep(i, n){
		cin >> v[i];
	}
	rep(i, n){
		cin >> c[i];
	}

	int x = 0, y = 0;
	rep(i, n){
		if(v[i] > c[i]){
			x += v[i];
			y += c[i];
		}
	}


	cout << x - y << endl;





    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//datatypes
	#define int long long
	#define vi vector<int>
	#define si set<int>
	#define vii vector<ii>
	#define ii pair<int,int>
	#define mii map<int,int>
	#define M 1000000007
	#define pi 3.141592653589793
	#define in(x) int x; cin>>x;
	#define sz(x) (int)x.size()
	#define fr first
	#define sc second
	#define pb push_back
	#define mkp make_pair
	#define inputFile \
	    freopen("input.txt", "r", stdin); 
	#define outputFile \
	    freopen("output.txt", "w", stdout)
	#define rep(i,a,b) for(int i=a; i<b; i++)
	#define trav(a) for(auto &x:a)
	#define test cout<<"hello\n";
	#define all(x) (x).begin(),(x).end()
	#define mem0(x) memset(x, 0, sizeof(x))
	#define mem1(x) memset(x, -1, sizeof(x))
	#define sa(x) std::sort(all(x))
	#define sd(x) std::sort(all(x),greater<int>())

signed solve()
{
	int n, wl;
	cin>>n>>wl;
	vi v(n+5),w(n+5);
	rep(i,0,n)cin>>w[i]>>v[i];
	int dp[n+5][100000+5];
	rep(i,0,n+5)
	rep(j,0,100005)
	dp[i][j]=1LL<<60;
	dp[0][0]=0;

	rep(i,0,n)
	{
		rep(j,0,100005)
		{
			if(j<v[i])
				dp[i+1][j]=dp[i][j];
			else
			{
				//cout<<"e";
				dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i]);
				/*if(dp[i+1][j]<=1000)
					cout<<dp[i+1][j]<<" i+1:"<<i+1<<" j"<<j<<endl;*/
			}
		}
	}
	int ans=0;
	rep(i,0,100005)
	{
		if(dp[n][i]<=wl)
			ans=i;
	}
	
	cout<<ans;


	return 0;
}

signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) solve();
	//cout << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

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

namespace ConsoleApp1
{
	class Program
	{
		static void Main(string[] args)
		{
			var inputs = Console.ReadLine().Split(' ');
			Console.ReadLine();
			var n = int.Parse(inputs[0]);
			var k = int.Parse(inputs[1]);

			int count = 0;
			while (true)
			{
				count++;
				if (n - k <= 0)
				{
					Console.WriteLine(count);
					return;
				}
				n = n - k + 1;
			}
		}
	}
}


Measured memory_bytes: 14688
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
using namespace std;
#define int long long


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

    int n,a,b; cin >> n >> a >> b;

    if(a > b){
        cout << 0 << endl;
        return 0;
    }
    if(a != b && n == 1){
        cout << 0 << endl;
        return 0;
    }
    int m = a * (n-1) + b;
    int M = a + b * (n-1);

    cout << M-m+1 << endl;
}



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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()

x = N / 1.08
if int(int(x)*1.08) == N:
    print(int(x))
elif int(ceil(x)*1.08) == N:
    print(ceil(x))
else:
    print(':(')


Measured memory_bytes: 3064
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> act(n, vector<int>(3, 0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> act[i][j];
		}
	}

	vector<vector<int>> dp(n+1, vector<int>(3, -1));
	dp[0][0] = dp[0][1] = dp[0][2] = 0;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			dp[i][j] = max(dp[i][j], max(dp[i - 1][(j + 1) % 3] + act[i - 1][j], dp[i - 1][(j + 2) % 3] + act[i - 1][j]));
		}
	}
	cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
	return 0;
}

Measured memory_bytes: 11136
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		long[]A = new long[N+1];
		string[] str = Console.ReadLine().Split();
		for(var i=0;i<N+1;i++){
			A[i] = long.Parse(str[i]);
		}
		long[,]D = new long[N+1,2];
		D[N,0] = A[N];
		D[N,1] = A[N];
		for(var i=N-1;i>=0;i--){
			D[i,0] = Math.Max(1,(D[i+1,0]+1)/2)+A[i];
			D[i,1] = D[i+1,1]+A[i];
		}
		if(D[0,0] > 1){
			Console.WriteLine(-1);
		} else {
			long ans = 1;
			long t = 1;
			for(var i=1;i<=N;i++){
				t = Math.Min(D[i,1],t*2);
				ans += t;
				t -= A[i];
			}
			Console.WriteLine(ans);
		}
	}
}

Measured memory_bytes: 29384
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#define REP(i, n) for(int i=0; i<(n); i++)
#define FOR(i, a, n) for(int i=(a); i<(n); i++)
using namespace std;

int main(){
    int a,b,c;cin >> a >> b >> c;
    string ans = a + b >= c ? "Yes":"No";
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
/*
      author : nishi5451
      created: 11.08.2020 01:10:02
*/

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


int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(a==b) cout << c << endl;
    else if(b==c) cout << a << endl;
    else if(c==a) cout << b << endl;
    return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{

     ll t=1,i,j,n,k,m;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  //  cin>>t;
    while(t--)
    {
      cin>>n;
      ll d=n/1000;
      d++;
      m=d*1000;
      if(m-n==1000)
        cout<<0;
      else
      cout<<m-n;
    }
}


Measured memory_bytes: 3688
def mount(l):
    if l == []:
        return True
    else:
        m = l.index(max(l))
        flag = 0
        for i in range(m):
            if l[i] > l[i+1]:
                flag = 1
        for i in range(m,len(l)-1):
            if l[i] < l[i+1]:
                flag = 1
        if flag == 0:
            return True
        else:
            return False
def count(l):
    if mount(l):
        if l != []:
            return(max(l))
        else:
            return 0
    else:
        cnt = min(l)
        l = list(map(lambda x:x-min(l),l))
        start = 0
        for i in range(len(l)):
            if l[i] == 0:
                cnt += count(l[start:i])
                start = i+1
            elif i == len(l)-1:
                cnt += count(l[start:])
        return(cnt)
N = int(input())
h = list(map(int,input().split()))
print(count(h))

Measured memory_bytes: 3064
import java.util.Scanner;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] a = new int[N + 1];
        for (int i = 0; i < M; i++) {
            a[sc.nextInt()] += 1;
            a[sc.nextInt()] += 1;
        }
        for (int i = 1; i <= N; i++) {
            System.out.println(a[i]);
        }
    }
}

Measured memory_bytes: 21844
#include<stdio.h>

int main(void)
{
    int a[1000000],b,s,n,m;
    scanf("%d",&s);
    a[0]=s;
    m=0;
    for(n=1;n<=1000000;n++){
        if(a[n-1]%2==0){
            a[n]=a[n-1]/2;
        }else{
            a[n]=3*a[n-1]+1;
        }
        for(b=1;b<=n-1;b++){
            if(a[n]==a[b-1]){
                m=n+1;
                break;
            }
        }
        if(m!=0){
            break;
        }
    }
    printf("%d\n",m);
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>
int main()
{
	char color[15];
	char warna[15];
	char RGB [15];
	int A, B;
	
	scanf("%s %s", &color, &warna);
	scanf("%d %d", &A, &B);
	scanf("%s", &RGB);
	
	if (strcmp(RGB,warna)==0) printf("%d %d", A, B-1);
	if (strcmp(RGB,color)==0) printf("%d %d\n", A-1, B);
	
	return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    int k, x;
    cin >> k >> x;

    if(k * 500 >= x)yn;
    return 0;
}
 
 


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n;
	cin>>n;
	int ans=0;
	int a=0,b=0,c=0;
	while(n--){
		string s;
		cin>>s;
		for(int i=0;i<=(int)s.size()-2;i++){
			if(s[i]=='A' && s[i+1]=='B') ans++;
		}
		if(s[0]=='B' && s[s.size()-1]=='A') c++;
		if(s[0]=='B' && s[s.size()-1]!='A') b++;
		if(s[s.size()-1]=='A' && s[0]!='B') a++;
	}
	if(c!=0){
		ans+=c-1;
	if(a>0){
		ans++; a--;
	}
	if(b>0){
		ans++; b--;
	}
	ans+=min(a,b);
	}
	else{
		ans+=min(a,b);
	}
	cout<<ans;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
    static void Main(string [] args)
    {
        var l = Console.ReadLine().Split(' ').Select(x => x.ToUpper()[0]);
        var result = "";
        foreach (var s in l) result += s;
        Console.WriteLine(result);
    }
}

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

#define         eps         10e-9
#define         pi          2*acos(0)
#define         P1          1e9+7
#define         P2          1e9+9
#define         lli         long long int

using namespace std;

///ISNNJB
int ara[200010],brr[100010];

void constructXOR(int n) {
    lli XOR = 0;
    for (int i = 0; i < n; i++)
        XOR ^= ara[i];
    ///cout<<XOR<<endl;

    for (int i = 0; i < n; i++)
        ara[i] = XOR ^ ara[i];
}

/**int fx[]={+1,-1,+0,+0};
int fy[]={+0,+0,+1,-1};
int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};*/

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

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    lli n;
    cin>>n;
    for (int i=0; i<n; i++)
        cin>>ara[i];
    constructXOR(n);

    for (int i = 0; i < n-1; i++)
        cout << ara[i] << " ";
    cout<<ara[n-1]<<endl;

    return 0;
}


Measured memory_bytes: 4452
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

#define CH(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)

using namespace std;

int T,P,R,tID,pID,tim;
string message;
int solv[55],pen[55], wap[55][505];

int main() {
  while(1){
    cin>>T>>P>>R;
    if(T==0&&P==0&&R==0) break;
    vector< pair<pair<int,int>,int> > v(T); //score,pen,tid
    REP(i,0,T){
      v[i].first.first = v[i].first.second = 0;
      v[i].second = i;
      REP(j,0,P) wap[i][j]=0;
    }
    REP(i,0,R){
      cin>>tID>>pID>>tim>>message;
      if(message=="CORRECT"){
        v[tID-1].first.first++;
        v[tID-1].first.second += wap[tID-1][pID-1]*1200+tim;
      }else{
        wap[tID-1][pID-1]++;
      }
    }
    sort(v.begin(),v.end());
    for(int score=P; 0<=score; score--){
      REP(i,0,v.size()){
        if(v[i].first.first==score) cout<<v[i].second+1<<" "<<v[i].first.first<<" "<<v[i].first.second<<endl;
      }
    }
  }

  return 0;
}

Measured memory_bytes: 3268
fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim_right().to_owned()
}

fn main() {
    let nums: Vec<u64> = read_line().split_whitespace().map(|x| x.parse().unwrap()).collect();
    let (x, a) = (nums[0], nums[1]);
    
    println!("{}", if x < a { 0 } else { 10 });
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
#define randIn(L,R) (((LL)rand()*rand())%(R-L)+L)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.14159265358979323846264338327950;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
    int x=0;
    char ch=' ';
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')flag=true;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return flag?-x:x;
}
int lcm(int a,int b)
{
	return a/__gcd(a,b)*b;
}
const int MAX_N=100005;
int sum[MAX_N];
bool is_prime[MAX_N];
void init()
{
	memset(is_prime,true,sizeof(is_prime));
	is_prime[0]=is_prime[1]=false;
	For(i,2,sqrt(MAX_N))
		if(is_prime[i])
			for(int j=i+i;j<MAX_N;j+=i)
				is_prime[j]=false;
	rep(i,0,MAX_N)
		if(is_prime[i] && is_prime[(i+1)/2])sum[i]=1;
	rep(i,1,MAX_N)
		sum[i]+=sum[i-1];
}
int main()
{
	init();
	int Q=read();
	while(Q--)
	{
		int l=read(),r=read();
		cout<<sum[r]-sum[l-1]<<endl;
	}
	return 0;
}




Measured memory_bytes: 1152
import math

K = int(input())
n = 0
A = []
for i in range(1, K+1):
    for j in range(1, K+1):
        A.append(math.gcd(i,j))
for a in A:
    for k in range(1, K+1):
        n += math.gcd(a, k)
print(n)

Measured memory_bytes: 69776
function Main(input){
    input = input.split("\n");
    var mem = input[0].split(" ").map(Number);
    input.shift();
    var tag = mem[1];
    for(var i=0;i<input.length;i++){
      input[i] = input[i].split(" ").map(Number);
    }
    input = input.sort(function(a,b){return a[0]-b[0];});
    var sum = 0;
    var ans = 0;
    for(i=0;true;i++){
      if(sum+input[i][1]<tag){
        sum += input[i][1];
        ans += input[i][0]*input[i][1];
      }else{
        ans += (tag-sum)*input[i][0];
        break;
      }
    }
   console.log(ans);
  }Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

Measured memory_bytes: 35056
#include <cstdio>
#include <cmath>
#include <iostream>
#include <complex>
#include <vector>
#include <algorithm>
#include <cfloat>
using namespace std;

typedef complex<double> P;
typedef const P &rP;
typedef vector<P> polygon;

inline double dot(rP va, rP vb){
	return real(va) * real(vb) + imag(va) * imag(vb);
}

inline double cross(rP va, rP vb){
	return real(va) * imag(vb) - imag(va) * real(vb);
}

inline int ccw(rP a, P b, P c) {
	b -= a;
	c -= a;
	if (cross(b, c) > 0)	 return +1;			 // counter clockwise
	if (cross(b, c) < 0)	 return -1;			 // clockwise
	if (dot(b, c) < 0)		 return +2;			 // c--a--b on line
	if (norm(b) < norm(c)) return -2;			 // a--b--c on line
	return 0;
}

P crosspoint(rP pa1, rP pa2, rP pb1, rP pb2){
	P da12 = pa2 - pa1;
	P db21 = pb1 - pb2;
	P dab1 = pb1 - pa1;
	double D = cross(da12, db21);

	return pa1 + da12 * (cross(dab1, db21) / D);
}

polygon convex_cut(const polygon &plg, rP a, rP b) {
	polygon ret;

	for (int i = 0; i < plg.size(); ++i) {
		P c = plg[i];
		P d = plg[(i + 1) % plg.size()];

		if (ccw(a, b, c) != -1) ret.push_back(c);
		if (ccw(a, b, c) * ccw(a, b, d) < 0){
			ret.push_back( crosspoint(a, b, c, d) );
		}
	}
	return ret;
}

double area(const polygon &pl){
	double sum = 0.0;
	for(int i = 2; i < pl.size(); ++i){
		sum += cross(pl[i-1] - pl[0], pl[i] - pl[0]);
	}
	return 0.5 * abs(sum);
}

int main(){
	double xa, ya;
	int dataset = 0;
	
	while( scanf("%lf%lf", &xa, &ya), xa != 0 ){
		polygon pl;
		pl.push_back( P(0.0, 0.0) );
		pl.push_back( P(0.0, 1e4) );
		pl.push_back( P(1e4, 1e4) );
		pl.push_back( P(1e4, 0.0) );

		P pa(xa, ya);

		double xb, yb;
		for(int i = 0; i < 2; ++i){
			scanf("%lf%lf", &xb, &yb);
			P pb(xb, yb);
			
			P vd = pb - pa;
			P pc = 0.5 * (pa + pb);
			P pd = pc + P(vd.imag(), -vd.real());
			
			if( ccw(pc, pd, pa) < 0 ){
				swap(pc, pd);
			}
			
			pl = convex_cut(pl, pc, pd);
		}

		
		printf("%d %f\n", ++dataset, area(pl) * 1e-8);
	}
}

Measured memory_bytes: 1252
#include<bits/stdc++.h>
#define ll long long
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
using namespace std;
 
int main()
{
    fast_io
    ll i,j,n,x,ans=0;
    string s;
    bool fA=0,fc=0,noAZ=0;
    cin>>s;
        if(s[0]!='A'||(s[1]>='A'&&s[1]<='Z')||(s[s.length()-1]>='A'&&s[s.length()-1]<='Z'))
   return cout <<"WA"<<endl,0;
    ll cntc=0,cap=0;
    for(i=1; i<s.length()-1; i++)
    {
    if(i>=2&&i<s.length()-1)
    {
        if(s[i]=='C') cntc++;
    }
    if(s[i]>='A'&&s[i]<='Z') cap++;
    }
 
if(cap>1)
   return cout <<"WA"<<endl,0;
    if(cntc!=1)
   return cout <<"WA"<<endl,0;
   return cout <<"AC"<<endl,0;
    return 0;
}
 
 
 

Measured memory_bytes: 3536
#define _USE_MATH_DEFINES // for C++  
#include <cmath> 
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <utility>
#include <set>
#include <random>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <functional>
#define LL long long


using namespace std;

int main() {
	int n, l;
	cin >> n >> l;
	vector<string> v(n);
	for (size_t i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	for (auto&& value : v)
	{
		cout << value;
	}
	cout << endl;
    return 0;
}   


Measured memory_bytes: 256
#include<stdio.h>


int main(){

  int n, a, b, c;
  int i;

  scanf("%d", &n);
  for(i=0;i<n;i++){
    scanf("%d %d %d", &a, &b, &c);
    if(a*a==b*b+c*c||b*b==a*a+c*c||c*c==a*a+b*b) printf("YES\n");
    else printf("NO\n");
  }
  
  return 0;
}

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

long long a[300005];

const int MOD = 1e9 + 7;

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    
    long long res = 0;
    
    for (int i = 0; i < 60; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if ((a[j] >> i) & 1LL) cnt++;
        }
        long long tot = 1LL * cnt * (n - cnt);
        tot %= MOD;
        long long p = (1LL << i) % MOD;
        res = (res + (tot * p) % MOD) % MOD;
    }
    
    printf("%lld\n", res);
}


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

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

  vector<int> W(N);

  for(int &i:W)
    cin >> i;

  int S2 = accumulate(W.begin(),W.end(),0);

  int m = S2;
  int m_abs = S2;

  for(int i = 0; i < W.size(); i++){
    m_abs = min(m_abs, abs(m - 2*W[i]));
    m -= 2*W[i];
  }

  cout << m_abs << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
const ll mod=1000000007;
int main(void){
    ll n;cin>>n;
    map<pair<ll,ll>,ll> mp;
    ll inv0=0;
    rep(i,n){
        ll x,y;cin>>x>>y;
        ll g=gcd(x,y);
        if(x==0&&y==0){
            inv0++;
            continue;
        }
        if(y<0){
            x*=-1;y*=-1;
        }
        x/=g;y/=g;
        mp[{x,y}]++;
    }
    
    vector<ll> s(n*2+10,1);//2^n
    rep(i,n*2) s[i+1]=(s[i]*2)%mod;
    ll res=1;
    for(auto& p:mp){
        ll a=p.first.first,b=p.first.second,x=p.second;
        if(x==0)continue;//すでに見られてる
        x+=mp[{-a,-b}];
        ll tmp=1;
        ll t=mp[{-b,a}]+mp[{b,-a}];
        tmp+=s[x]-1;tmp%=mod;
        tmp+=s[t]-1;tmp%=mod;
        mp[{-b,a}]=0;mp[{b,-a}]=0;mp[{-a,-b}]=0;
        res*=tmp;
        res%=mod;
    }
    res=(res+mod-1)%mod;
    res+=inv0;
    res%=mod;
    cout<<res<<endl;
}


Measured memory_bytes: 56092
import sys
input = sys.stdin.buffer.readline

INF = 10**18

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

XY.sort()

ans = 0
x0, y0 = XY[0]
m1 =  -x0+y0# 今ままでのmax
m2 = x0+y0
for x, y in XY:
    ans = max(ans, x+m1 - y)
    ans = max(ans, y - (-x+m2))
    m1 = max(m1, -x+y)
    m2 = min(m2, x+y)
print(ans)

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

using namespace std;
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; ++i)
#define rep1(i,h) for(int i = 0; i <= h; ++i)
#define rep2(i,k,h) for(int i = k; i < h; ++i)
#define rep3(i,k,h) for(int i = k; i <= h; ++i)
#define INF LONG_LONG_MAX // long long INF
#define inf INT_MAX // int inf

typedef pair<int,int> int_pair;
typedef pair<string,string> string_pair;


int main() {
    int n;
    cin >> n;
    ll ans = 0;
    rep2(i,1,n) {
        ans += i;
    }
    cout << ans << endl;
    return 0;
}



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




typedef pair<long double, long double> point;
typedef pair<point, long double >circle;

int main() {
	point S, T;
	cin >> S.first >> S.second >> T.first >> T.second;
	long long int N;
	cin >> N;
	vector<circle>D( N + 2 );
	for( size_t i = 0; i < N; i++ ) {
		cin >> D[i].first.first >> D[i].first.second >> D[i].second;
	}
	D[N] = make_pair( S, 0 );
	D[N + 1] = make_pair( T, 0 );
	vector<vector<long double>>M( N + 2, vector<long double>( N + 2, LDBL_MAX / 6 ) );
	for( size_t i = 0; i < N + 2; i++ ) {
		M[0][0] = 0;
	}
	for( size_t i = 0; i < N + 2; i++ ) {
		for( size_t j = i + 1; j < N + 2; j++ ) {
			M[i][j] = max( sqrtl( powl( (D[i].first.first - D[j].first.first), 2 ) + powl( (D[i].first.second - D[j].first.second), 2 ) ) - (D[i].second + D[j].second), 0.L );
			M[j][i] = M[i][j];
		}
	}
	priority_queue<pair<long double, long long int>, vector<pair<long double, long long int>>, greater<pair<long double, long long int>>>que;
	que.push( make_pair( 0, N ) );
	vector<long double>ans( N + 2, LDBL_MAX / 6 );
	ans[N] = 0;
	while( que.size() ) {
		auto now = que.top(); que.pop();
		if( now.second == N + 1 ) {
			cout << fixed << setprecision( 20 ) << now.first << endl;
			break;
		}
		if( ans[now.second] != now.first ) {
			continue;
		}
		for( size_t i = 0; i < N + 2; i++ ) {
			if( ans[i] > now.first + M[now.second][i] ) {
				ans[i] = now.first + M[now.second][i];
				que.push( make_pair( ans[i], i ) );
			}
		}
	}

}

Measured memory_bytes: 24312