akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

int a[300][300];

void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);  a[i][j]--;
        }
    }

    int l = 0, r = n;   //r:ok
    while (r - l > 1) {
        int mm = (l + r) / 2;

        vector<int> curr(n);
        vector<int> flag(m);
        int fin = 0;
        while (1) {
            vector<vector<int> > z(m);
            for (i = 0; i < n; i++) {
                while (curr[i] < m && flag[a[i][curr[i]]]) {
                    curr[i]++;
                }
                if (curr[i] == m) {
                    fin = 1;
                    break;
                }
                int tmp = a[i][curr[i]];
                assert(flag[tmp] == 0);
                z[tmp].push_back(i);
            }
            if (fin) {
                break;
            }
            int del = 0;
            for (i = 0; i < m; i++) {
                if (z[i].size() > mm) {
                    for (j = 0; j < (int)z[i].size(); j++) {
                        int id = z[i][j];
                        curr[id]++;
                    }
                    flag[i] = 1;
                    del = 1;
                }                
            }
            if (del == 0) {
                break;
            }
        }
        if (fin) {
            l = mm;
        }
        else {
            r = mm;
        }
    }
    printf("%d\n", r);



    return;
}


int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <functional>
using namespace std;

typedef long long ll;


ll a[100003], b[100003];

int main() {
	int n; cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < n; ++i) cin >> b[i];
	ll s = 0, t = 0;
	for (int i = 0; i < n; ++i) {
		if (a[i] < b[i]) s += (b[i] - a[i]) / 2;
		if (a[i] > b[i]) t += a[i] - b[i];
	}
	cout << (s - t >= 0 ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 384
for i in iter(input, '0 0'):
    height, width = list(map(int, i.split()))
    
    for h in range(height):
        line = ''
        is_vertical_side_line = h == 0 or h == height - 1
        for w in range(width):
            is_horizontal_side_line = w == 0 or w == width - 1
            
            if is_vertical_side_line or is_horizontal_side_line:
                line += '#'
            else:
                line += '.'
            
        print(line)
    
    print()


Measured memory_bytes: 5608
a = int(input())
res = (1 + a) * a // 2
three, five, fifteen = 0, 0, 0
if res >= 3:
    three = (3 + a // 3 * 3) * (a // 3) //2
if res >= 5:
    five = (5 + a // 5 * 5) * (a // 5) //2
if res >= 15:
    fifteen = (15 + a // 15 * 15) * (a // 15) //2

print(res - three - five + fifteen)

Measured memory_bytes: 61836
#include<stdio.h>
int main(void)
{
	int m, f, r;
	int x;
	while (1) {

		scanf("%d %d %d", &m, &f, &r);
		x = m + f;
		if (m == -1 && f == -1 && r == -1) {
			break;
		}

		if (m == -1 || f == -1) {
			printf("F\n");
		}
		else if (x >= 80) {
			printf("A\n");
		}
		else if (x >= 65) {
			printf("B\n");
		}
		else if (x >= 50) {
			printf("C\n");
		}
		else if (x >= 30) {
			if (r >= 50) {
				printf("C\n");
			}
			else {
				printf("D\n");
			}
		}
		else if (x < 30) {
			printf("F\n");
		}
	}

	return(0);
}


Measured memory_bytes: 2060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try (Scanner sc = new Scanner(System.in)) {
			int d = sc.nextInt();
			int n = sc.nextInt();
			
			int result = 0;
			switch (d) {
			case 0:
				if (n == 100) {
					result = 101;
				} else {
					result = n;
				}
				break;
			case 1:
				if (n == 100) {
					result = 10100;
				} else {
					result = 100 * n;
				}
				break;
			case 2:
				if (n == 100) {
					result = 1010000;
				} else {
					result = 10000 * n;
				}
				break;
			}
			
			System.out.println(result);
		}

	}

}

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

using namespace std;

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

#define ALL(obj)	(obj).begin(),(obj).end()

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

typedef pair<int,int>			P;

#define LINF		((ll)1 << 63 -1)
#define INF 		2000000007
#define MINF		-2000000007
#define MAX 		100005

const int MOD = 1e9+7;
// テンプレ終了
//====================================================================//


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

	map<int,int> m;
	REP(i,N){
		int t;cin>>t;
		m[t]++;
	}

	int ans = 0;
	for(auto itr = m.begin();itr != m.end();++itr){
		if(itr->second%2==1)ans++;
	}

	cout << ans << endl;

	return 0;
}




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

int main() {
    int h, w;
    char s[50][50];
    cin >> h >> w;
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            cin >> s[i][j];
        }
    }
    //上下左右を調べるための配列を用意する
    const int dx[4] = {0, 0, 1,-1};
    const int dy[4] = {1,-1, 0, 0};
    //can1が最後までtrueのままならYesを出力する
    bool can1 = true;
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            if (s[i][j] == '.') continue;
            /*'#'が出たら上下左右に'#'があるかどうかを調べる。
            なかったらループから出る*/
            bool can2 = false;
            for (int d=0; d<4; d++) {
                int ni = i + dy[d];
                int nj = j + dx[d];
                //以下二文で枠外を探索してしまう場合を除外する
                if (ni < 0 || ni >= h) continue;
                if (nj < 0 || nj >= w) continue;
                //'#'があったらcan2をtrueにして続行。can2がfalseのままならループから出る。
                if (s[ni][nj] == '#') can2 = true;
            }
            if (!can2) {
                can1 = false;
                break;
            }
        }
        if (!can1) break;
    }
    
    if (can1) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

using namespace std;

#define ll long long
#define ld long double
#define pb push_back

int main()
{
	ios_base::sync_with_stdio(false);
	int a, b, c;
	cin >> a >> b >> c;
	bool can = 0;
	if (a + b == c)
		can = 1;
	if (c + b == a)
		can = 1;
	if (a + c == b)
		can = 1;
	if (can)
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

def bellman_ford(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = {i: defaultdict(int) for i in range(N)}
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = [INF]*N
    prev = [-1]*N
    dist[s] = 0
    for n_iterations in range(N):
        updated = False
        for v in V:
            d = dist[v]
            if d != INF:
                for u, c in E[v].items():
                    temp = d + c
                    if dist[u] > temp:
                        updated = True
                        dist[u] = temp
                        prev[u] = v
        if not updated: # the minimum costs are already stored in dist
            break
    else: # the above loop is not broken if and only if there exists a negative cycle
        return None
    return dist

INF = float('inf')
N, M, r = map(int, input().split())
E = {i: defaultdict(int) for i in range(N)}
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a][b] = c
V = list(range(N))
dist = bellman_ford(V, E, r)
if dist is None:
    print('NEGATIVE CYCLE')
else:
    for d in dist:
        if d == INF: print('INF')
        else: print(d)


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

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

//map<int,int> mmap;


int main(){

    //freopen("test.in","r",stdin);

    string str;
    cin>>str;

    int st,ed,ssize = str.size();
    st = 0;
    ed = ssize-1;
    int ct=0;
    while(st<ed){
        if(str[st]!=str[ed]) ct++;
        st++;
        ed--;
    }

    cout<<ct<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

vector<vector<int>> g;

int dist[202020];

void dfs1(int v, int d = 0, int f = -1) {
  dist[v] = d;
  for(auto to: g[v]) {
    if(to == f) continue;
    dfs1(to, d + 1, v);
  }
}

int main() {
  int N;
  cin >> N;
  g.resize(N);
  for(int i = 0;i < N - 1;i++) {
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  dfs1(0);
  int r = 0;
  for(int i = 0;i < N;i++) {
    if(dist[r] < dist[i]) r = i;
  }
  dfs1(r);
  int MAX = 0;
  for(int i = 0;i < N;i++) {
    MAX = max(MAX, dist[i]);
  }

  int ans = MAX + 1;
  vector<bool> dp(202020, false);
  dp[0] = false;
  dp[1] = true;
  dp[2] = false;
  for(int i = 3;i < 202020;i++) {
    if(dp[i - 2] && dp[i - 1]) dp[i] = false;
    else dp[i] = true;
  }

  if(dp[ans]) {
    cout << "First" << endl;
  }
  else {
    cout << "Second" << endl;
  }
}


Measured memory_bytes: 21376
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string ss;
    cin >> ss;

    if( (ss[2] == ss[3]) && (ss[4] == ss[5]) ){
        cout << "Yes" << endl;
    }else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A;
  int B;
  cin >> A;
  cin >> B;
  int X;
  for ( int i = A ; i <= B ; i++ ) {
    int C;
    int D;
    int E;
    int F;
    int G;
    C = i / 10000;
    D = ( i - ( i / 10000 ) * 10000 ) / 1000;
    E = ( ( i - ( i / 10000 ) * 10000 ) - ( ( i - ( i / 10000 ) * 10000 ) / 1000 * 1000 ) ) / 100;
    F = ( ( ( i - ( i / 10000 ) * 10000 ) - ( ( i - ( i / 10000 ) * 10000 ) / 1000 * 1000 ) ) - ( ( i - ( i / 10000 ) * 10000 ) - ( ( i - ( i / 10000 ) * 10000 ) / 1000 * 1000 ) ) / 100 * 100 ) / 10;
    G = i - ( C * 10000 + D * 1000 + E * 100 + F * 10 );
    if ( C == G ) {
      if ( D == F ) {
        X = X + 1;
      }
    }
  }
  cout << X << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
//#define gcd __gcd
//#define lcm(a, b) ((a) * (b) / gcd((a), b))
#define all(x) x.begin(), x.end()
#define rep(i, x, n) for (ll i = x; i < n; i++)
#define fastio() ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0)
#define endl '\n'

typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> ii;
typedef vector<pair<int, int> > vii;

template <class T> inline T RD(T &a) {T x; cin >> x; return a = x;}

//OJ freopen Template
void OJF(const char* inp, const char* out) {
	if (strlen(inp) > 0) freopen(inp, "r", stdin);
	if (strlen(out) > 0) freopen(out, "w", stdout);
}

const float pi = acos(-1);

signed main()
{
    //OJF("TRAIGLE.inp", "TRIAGLE.out");
	fastio();

	float r; cin >> r;
    cout << pi * 2 * r;
}


Measured memory_bytes: 3756
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn=new Scanner(System.in);
		int a=scn.nextInt();
		int b=scn.nextInt();
		if(a-2*b<=0) {
			System.out.println(0);
		}else{
			System.out.println(a-2*b);
		}
	}

}


Measured memory_bytes: 21972
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>

using Point = std::vector<int>;

double distance(const Point& p1, const Point& p2)
{
  const auto d = p1.size();
  int s = 0;
  for (auto i = 0u; i < d; ++i) {
    const auto x = p1[i] - p2[i];
    s += x * x;
  }
  return std::sqrt(s);
}

int solve(const std::vector<Point>& points)
{
  int result = 0;
  for (auto i = 0u; i < points.size(); ++i) {
    for (auto j = i + 1; j < points.size(); ++j) {
      const auto dista = distance(points[i], points[j]);
      int x = static_cast<int>(dista);
      if (x * x == dista * dista) result++;
    }
  }
  return result;
}

int main()
{
  int n, d;
  std::cin >> n >> d;

  std::vector<Point> points(n, Point(d));
  for (auto& p : points) {
    for (auto& e : p) {
      std::cin >> e;
    }
  }

  std::cout << solve(points) << std::endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;


int main(){
  int n;
  cin >> n;
  vector<vector<int> > a(2, vector<int>(n));
  rep(i, n) cin >> a[0][i];
  rep(i, n) cin >> a[1][i];
  vector<vector<int> > dp(2, vector<int>(n + 1));
  dp[0][0] = a[0][0];
  dp[1][0] = a[1][0] + dp[0][0];
  for(int i = 1; i < n; ++i){
    dp[0][i] = dp[0][i - 1] + a[0][i];
    dp[1][i] = max(dp[0][i], dp[1][i - 1]) + a[1][i];
  }
  cout << dp[1][n - 1] << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        String s = scanner.next();
        char[] c = s.toCharArray();
        if (c[K - 1] == 'A') {
            c[K - 1] = 'a';
        } else if (c[K - 1] == 'B') {
            c[K - 1] = 'b';
        } else {
            c[K - 1] = 'c';
        }
        System.out.println(String.valueOf(c));
    }

}


Measured memory_bytes: 21588
var
 x,max,min,i,n,k,s:longint;
 sum:int64;
 a,b:array[0..200001] of longint;
procedure kp(l,r:longint);
var
 i,j,t,m:longint;
begin
 i:=l; j:=r;
 m:=a[(l+r) div 2];
 repeat
  while a[i]<m do inc(i);
  while a[j]>m do dec(j);
  if i<=j then
   begin
    t:=a[i]; a[i]:=a[j]; a[j]:=t;
    inc(i); dec(j);
   end;
 until i>j;
 if l<j then kp(l,j);
 if i<r then kp(i,r);
end;
begin
 min:=maxlongint;
 readln(n,k);
 for i:=1 to n do 
  begin
   read(x);
   inc(b[x]);
   if x>max then max:=x;
   if x<min then min:=x;
  end;
 for i:=min to max do
  if b[i]<>0 then 
   begin
    inc(s);  
    a[s]:=b[i];
   end;
 kp(1,s);
 for i:=1 to s-k do
  sum:=sum+a[i];
 writeln(sum);
end.

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

long long dp[101][8];
const int mod = 1000000007;

bool valid(int pattern) {
  int before = 0;
  int current;
  while(pattern !=0) {
    current = pattern % 2 == 1 ? 1 : 0;
    if(before == 1 && current == 1) {
      return false;
    }
    before = current;
    pattern = pattern >> 1;
  }
  return true;
} 

/**
 * h 縦棒のながさ + 1 
 * w 平行な縦線
 * k 最終的にたどり着くぼうの番号
 */
long long number_of_amidakuji(int h, int w, int k) {
  for(int i =0;i<101;i++) {
    for(int j=0;j<8;j++) {
      dp[i][j] = 0;
    }
  }
  dp[0][0] = 1;

  for(int i=0;i<h;i++) {
    for(int j=0;j<w;j++) {
      for(int a=0;a<(1 << (w-1));a++) {
	if (!valid(a))
	  continue;
	if(j==0) {
	  if(a & 1) {
	    dp[i+1][j+1] += dp[i][j] % mod;
	    dp[i+1][j+1] %= mod;
	    continue;
	  }
	  dp[i+1][j] += dp[i][j] % mod;
	  dp[i+1][j] %= mod;
	  continue;
	}
	if(j==w-1) {
	  if(a & (1 << (w-2))) {
	    dp[i+1][j-1] += dp[i][j] % mod;
	    dp[i+1][j-1] %= mod;
	    continue;
	  }
	  dp[i+1][j] += dp[i][j] % mod;
	  dp[i+1][j] %= mod;
	  continue;
	}
	if(a & (1 << (j-1))) {
	  dp[i+1][j-1] += dp[i][j] % mod;
	  dp[i+1][j-1] %= mod;
	  continue;
	}
	if(a & (1 << j)) {
	  dp[i+1][j+1] += dp[i][j] % mod;
	  dp[i+1][j+1] %= mod;
	  continue;
	}
	dp[i+1][j] += dp[i][j] % mod; 
	dp[i+1][j] %= mod;
      }
    }
  }
  return dp[h][k-1];
}

int main() {
  int h, w, k;
  cin >> h;
  cin >> w;
  cin >> k;
  cout << number_of_amidakuji(h, w, k);
}

Measured memory_bytes: 256
/* bellman_ford.cpp
    ベルマンフォード法で、ある頂点から各頂点への最短距離を求めるアルゴリズム
    負の辺が含まれる場合も適用でき、負の閉路も検出可能

    始点から終点に行くまでに通らない負の閉路は検出したくない時:
        http://sigma1113.hatenablog.com/entry/2019/08/12/130042

    verified: AOJ GRL_1_B
        http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B
*/

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

struct Edge {
    long long from;
    long long to;
    long long cost;
};
using Edges = vector<Edge>;
const long long INF = 1LL << 60;

/* bellman_ford(Es,s,t,dis)
    入力: 全ての辺Es, 頂点数V, 開始点 s, 最短経路を記録するdis
    出力: 負の閉路が存在するなら ture
    計算量：O(|E||V|)
    副作用：dis が書き換えられる
*/
bool bellman_ford(const Edges &Es, int V, int s, vector<long long> &dis) {
    dis.resize(V, INF);
    dis[s] = 0;
    int cnt = 0;
    while (cnt < V) {
        bool end = true;
        for (auto e : Es) {
            if (dis[e.from] != INF && dis[e.from] + e.cost < dis[e.to]) {
                dis[e.to] = dis[e.from] + e.cost;
                end = false;
            }
        }
        if (end) break;
        cnt++;
    }
    cnt = 0;
    while (cnt < V) {
        bool end = true;
        for (auto e : Es) {
            if (dis[e.from] != INF && dis[e.from] + e.cost < dis[e.to]) {
                dis[e.to] = -INF;
                end = false;
            }
        }
        if (end) break;
        cnt++;
    }
    return dis[V - 1] == -INF;
}

int main() {
    int V, E;
    cin >> V >> E;
    Edges Es;
    for (int i = 0; i < E; i++) {
        long long s, t, d;
        cin >> s >> t >> d;
        s--, t--;
        Es.push_back({s, t, -(d)});
    }
    vector<long long> dis;
    if (bellman_ford(Es, V, 0, dis)) {
        cout << "inf" << endl;
    } else {
        cout << -dis[V - 1] << endl;
    }

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1001001001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

int main()
{
    int n;
    cin >> n;
    vector<pair<ll, ll>> objs(n);
    for (int i = 0; i < n; i++)
    {
        ll x, l;
        cin >> x >> l;
        objs[i].first = x - l;
        objs[i].second = x + l;
    }
    sort(objs.begin(), objs.end());
    ll right = -LINF;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (objs[i].first >= right)
        {
            right = objs[i].second;
            ++ans;
        }
        else
        {
            if (objs[i].second < right)
            {
                right = objs[i].second;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
};

Measured memory_bytes: 4828
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
#include <map>
#include <array>
#include <cmath>

long long PRIME = 1e9 + 7;
using namespace std;

vector<vector<int>> E;


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

    bool check = true;
    int sum = 0;
    int count = N + 1;

    for(int i = 1; i <= N; ++i){
        int L;
        cin >> L;
        sum += L;
        if(sum > X && check){
            check = false;
            count = i;
        }
    }

    cout << count;
}



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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}


int main(void){
    COMinit();
    int N; cin >> N;
    ll X[N]; rep(i, N) cin >> X[i];
    //区間i(1 <= i <= N-1)を通るスライムの数の期待値をC_iとする
    //C_i = (1/i) * (C_(i-1) + 1) + (i-1/i) * C_(i-1) = C_(i-1) + (1/i), C_1 = 1
    //C_i = 1 + 1/2 + ... + 1/i
    //これに(N-1)!をかける
    ll dist[N];
    for(int i = 1; i < N; i++){
        dist[i] = X[i] - X[i-1];
    }
    ll fac[N]; fac[1] = 1;
    for(int i = 2; i < N; i++){
        fac[i] = (fac[i-1]*i) % mod;
    }
    ll sum[N+1]; sum[1] = fac[N-1];
    for(int i = 2; i < N; i++){
        sum[i] = (sum[i-1] + fac[N-1]*inv[i]) % mod;
    }
    ll ans = 0;
    for(int i = 1; i < N; i++){
        ans = (ans + (dist[i]*sum[i] % mod)) % mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 15360
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

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



















int main(){
    ll n, a;
    cin >> n >> a;
    cout << ((n % 500 <= a)? "Yes" : "No") << endl;
}

Measured memory_bytes: 384
#include<stdio.h>
typedef struct Node{
  int parent,left,right;
}Node;  
Node T[100000];
int n,D[100000];
void print(int p){
  int i,s;
  printf("node %d: parent = %d, depth = %d, ", p, T[p].parent, D[p]);
  if(T[p].parent == -1)
    printf("root, [");
  else if(T[p].left == -1)
    printf("leaf, [");
 else
    printf("internal node, [");
  s = T[p].left;
  for(i = 0; s != -1; i++, s = T[s].right){
    if(i)
      printf(", "); 
    printf("%d", s);
  } 
  printf("]\n");
} 
int depth(int x, int y){
  D[x] = y;
  
  if(T[x].right != -1)
    depth(T[x].right, y);
 
  if(T[x].left != -1)
    depth(T[x].left, y+1);
}
int main(){
  int a,b,c,left,right,i,j;
  scanf("%d", &n);
  for(i = 0; i < n; i++)
    T[i].parent = T[i].left = T[i].right = -1;   
  for(i = 0; i < n; i++){
    scanf("%d%d", &a, &b);    
    for(j = 0; j < b; j++){
      scanf("%d", &c); 
      if(j == 0)
	T[a].left = c;    
      else
	T[left].right = c;  
      left = c;
      T[c].parent = a;
    }
  }
  for(i = 0; i < n; i++){
    if(T[i].parent == -1)
      right = i;
  }
  depth(right, 0);
  for(i = 0; i < n; i++)
    print(i);
  return 0;
}

Measured memory_bytes: 5296
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define pii pair<int,int>
#define prec(n) fixed<<setprecision(n)
#define MOD 1000000007
#define eps 1e-8
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &a){
    return out<<"("<<a.first<<","<<a.second<<")";}
template<class A> ostream& operator<<(ostream& out, const vector<A> &a){
	out<<"";for(auto it=a.begin();it!=a.end();it++){if(it!=a.begin())out<<" ";out<<*it;}out<<"";
	return out;}
template<class A, class B> istream& operator>>(istream& in, pair<A,B> &a){in>>a.first>>a.second;return in;}
template<class A> istream& operator>>(istream& in, vector<A> &a){for(A &i:a)in>>i;return in;}
//ifstream cinn("input.txt");ofstream coutt("output.txt");

signed main(){
    FASTER;
    int N,W;cin>>N>>W;
    int w[N],v[N],dp[N+1][W+1];
    for(int i=0;i<N;i++)cin>>w[i]>>v[i];

    memset(dp,0,sizeof(dp));

    for(int i=1;i<=N;i++){
        for(int j=0;j<=W;j++){
            if(j-w[i-1]>=0)dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
            else dp[i][j]=dp[i-1][j];
        }
    }

    cout<<dp[N][W];

}


Measured memory_bytes: 79232
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ld long double
#define f(i,from,to) for(int i=from;i<to;++i)
#define endl '\n'
#define tie() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int main()
{
    //tie();
    ll t=1;
    //cin>>t;
    while(t--)
    {
      ll n,sum=0,ct=0,m,l,r,k,ans=0;
      cin>>n;
      cout<<n+n*n+n*n*n<<endl;

    }
    return 0;
}


Measured memory_bytes: 3632
import heapq
inf = 10**20
h = 2500
n, m, s = map(int, input().split())
s = min(h-1, s)
# A[i][j]=iからjへのコスト
A = [[inf for j in range(n)] for i in range(n)]
# B[i][j]=iからjへの時間
B = [[inf for j in range(n)] for i in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    A[u-1][v-1] = a
    A[v-1][u-1] = a
    B[u-1][v-1] = b
    B[v-1][u-1] = b
CD = [tuple(map(int, input().split())) for i in range(n)]
C = [c for c, d in CD]
D = [d for c, d in CD]
# G[i,x][j,y]=状態(i,x)から(j,y)に変わるのにかかる時間
G = {(i, x): {} for i in range(n) for x in range(h)}
for i in range(n):
    for j in range(n):
        for x in range(h):
            if i == j:
                G[i, x][i, x] = 0
                if x-1 >= 0:
                    G[i, x][i, x-1] = 0
                if x+C[i] < h:
                    G[i, x][i, x+C[i]] = D[i]
            elif x >= A[i][j]:
                G[i, x][j, x-A[i][j]] = B[i][j]
# T[i,x]=状態(0,s)から(i,x)にかかる時間
T = {(i, x): inf for i in range(n) for x in range(h)}
T[0, s] = 0
Q = [(0, (0, s))]
heapq.heapify(Q)
while Q:
    _, (i, x) = heapq.heappop(Q)
    for j, y in G[i, x].keys():
        if T[i, x]+G[i, x][j, y] < T[j, y]:
            T[j, y] = T[i, x] + G[i, x][j, y]
            heapq.heappush(Q, (T[j, y], (j, y)))
for i in range(1, n):
    print(T[i, 0])


Measured memory_bytes: 174108
#include<bits/stdc++.h>
using namespace std;
#define ll  long long int
#define ld long double
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,a) REP(i,0,a)
#define REV(i,a,b) for(i=a-1;i>=b;i--)
#define rev(s) reverse(s.begin(),s.end())
#define pb push_back
#define mp make_pair
#define ord(v) sort(v.begin(),v.end());
const ll MAXN=1e6+10;
#define MAX 2*1e9
#define fi first
#define se second
#define pi 3.141592653589793238
#define rem 1000000007
#define eps 1e-9
#define endl '\n'
#define lb lower_bound
#define ub upper_bound
#define print(stuff) cout << stuff << endl
#define printc(stuff) for(auto x: stuff) cout << x << " "; cout << endl;
#define printPrec(stuff) cout << fixed << setprecision(15) << stuff << endl;
#define inf 0x3f3f3f3f3f3f3f3f

/*****Some Useful Functions*****/
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;
}
ll binpow(ll a,ll b,ll r)
{
    a%=r;
    ll res=1;
    while(b>0)
    {
        if(b&1)
            res=(res*a)%r;
        a=(a*a)%r;
        b>>=1;
    }
    return res;
}
/*****Some Useful Functions*****/

// fflush(stdout);
//lower_bound,upper_bound,equal_range


void raa_j_shh(void);
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
    cout << fixed << setprecision(10);
    ll t=1;
    // cin>>t;
    while(t--) raa_j_shh();    
    return 0;
 } 

/*********El codigo comienza aqui*********/


void raa_j_shh()
{
    ll n,m,i,j;
    cin>>n>>m;
    char a[n][m];
    ll dp[n][m];
    rep(i,n)
    rep(j,m)
    cin>>a[i][j];
    dp[0][0]=1;
    for(i=1;i<n;i++)
    {
        if(a[i][0]=='.')
           { if(dp[i-1][0]==1)
                    dp[i][0]=1;
             else dp[i][0]=0;
            }
        else dp[i][0]=0;
    }
    for(i=1;i<m;i++)
    {
        if(a[0][i]=='.')
           { if(dp[0][i-1]==1)
                    dp[0][i]=1;
             else dp[0][i]=0;
            }
        else dp[0][i]=0;
    }
    for(i=1;i<n;i++)
    {
        for(j=1;j<m;j++)
        {
            if(a[i][j]=='.')
               { dp[i][j]=dp[i-1][j]+dp[i][j-1];dp[i][j]%=rem;}
            else dp[i][j]=0;
        }
    }
    cout<<dp[n-1][m-1]%rem<<endl;
   return;
}


/*********El codigo termina aqui**********/ 

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

namespace CSharpSample01
{

	class Program
	{

		static void Main(string[] args)
		{
			var inputNum = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

			var A = inputNum[0];
			var B = inputNum[1];
			var C = inputNum[2];
			var D = inputNum[3];

			var nextFlag = true;

			while (nextFlag)
			{
				C = C - B;
				if(C <= 0)
				{
					Console.WriteLine("Yes");
					nextFlag = false;
					break;
				}

				A = A - D;
				if (A <= 0)
				{
					Console.WriteLine("No");
					nextFlag = false;
					break;
				}
			}

		}
	}
}

Measured memory_bytes: 28240
#include <iostream>
#include<string>

using namespace std;

int main() {
	int h,w,i,j,k;
    string ss;

    while (1) {
        cin >> h >> w;
        if (w == 0 && h == 0){
            break;
        }

        for (i = 0; i < h; i ++){
            
            if (i%2 == 0) {
                for (j = 0; j < w; j++) {
                    if (j%2 ==0) cout << "#";
                    else cout << ".";
                }
            }

            else if (i%2 == 1) {
                for (j = 0; j < w; j++) {
                    if (j%2 ==1) cout << "#";
                    else cout << ".";
                }
            }
            cout << endl;

            
        }
        cout << endl;


    
    }
    return 0;

}


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

typedef long long ll;
typedef long double ld;
typedef double db;
int n,m;
	int a[200000];
	int x[200000],y[200000];
vector <int> sl[200000];
int ans=0;
bool p[200000];

void bfs(int beg){
    int vert[400000];
    p[beg]=1;
    vert[0]=beg;
    int j1,j2;
    j1=0;
    j2=1;
    while(j2>j1){
        vector <int> g= sl[vert[j1]];
        for(int i=0;i<g.size();i++){
            if(p[g[i]]==1) continue;
            vert[j2]=g[i];
            p[g[i]]=1;
            j2++;
        }
        j1++;
    }
   // cout<<endl;
   // for(int i=0;i<j2;i++){
    //    cout<<vert[i]<<" ";
   // }
   // cout<<"     "<<j2<<endl;
    int a1[400000];
    for(int i=0;i<j2;i++){
        a1[i]=a[vert[i]];
    }
    sort(a1,a1+j2);
    sort(vert,vert+j2);
    int b1[200000];
    int b2[200000];
    int k1=0,k2=0;
    for(int i=0;i<j2-1;i++){
        if(a1[i]!=a1[i+1]) {
            b1[k1]=a1[i];
            k1++;
        }
    }
    b1[k1]=a1[j2-1];
    k1++;
    for(int i=0;i<j2-1;i++){
        if(vert[i]!=vert[i+1]) {
            b2[k2]=vert[i];
            k2++;
        }
    }
    b2[k2]=vert[j2-1];
    k2++;
   // for(int i=0;i<3;i++){
    //    cout<<b1[i]<<" "<<b2[i]<<endl;
   // }
    int h1=0,h2=0;
    while(h1<k1&&h2<k2){
        if(b1[h1]<b2[h2]){
            h1++;
            continue;
        }
        if(b1[h1]>b2[h2]){
            h2++;
            continue;
        }
        if(b1[h1]==b2[h2]){
            h1++;
            h2++;
            ans++;
        }
    }
}
int main() {
	//ios_base::sync_with_stdio(false);
	//cout<<setprecision(20);
	cin>>n>>m;
	for(int i=0;i<n;i++){
	    cin>>a[i];
	    a[i]--;
	}
	for(int i=0;i<m;i++){
	    cin>>x[i]>>y[i];
	    sl[x[i]-1].push_back(y[i]-1);
	    sl[y[i]-1].push_back(x[i]-1);
	}
	for(int i=0;i<n;i++){
	    if(p[i]==1) continue;
	    bfs(i);
	  //  cout<<ans<<endl;
	}
	cout<<ans;
	return 0;
}

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

int main()
{
	int N;
	double A[100];
	double a = 0;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		a += 1 / A[i];
	}

	a = 1 / a;

	cout << a;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

using namespace std;

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

const ll mod = 1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;   // INFの値は1152921504606846976

int main()
{
    int n;
    cin >> n;
    cout << (n/500) * 1000 + ((n%500)/5) * 5;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    bool can = true;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int ai;
        cin >> ai;
        if (ai % 2 == 0)
            can &= (ai % 3 == 0 || ai % 5 == 0);
    }
    if (can)
        cout << "APPROVED";
    else
        cout << "DENIED";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int n,k;
  cin >> n >> k;
  string s;
  cin >> s;
  char c = 0;
  vector<char> r;
  ll ans = 0;
  rep(i,n){
    if(c == s[i]) ans++;
    c = s[i];
  }
  ans=min(ans+2*k,(ll)n-1);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3724
n, q = map(int, input().split())
s = input()
sl = len(s)
ac_cnts = [0]
cnt = 0
for i in range(0, sl-1):
    if s[i] == 'A' and s[i+1] == 'C':
        cnt += 1
    ac_cnts.append(cnt)
for i in range(q):
    l, r = map(int, input().split())
    print(ac_cnts[r-1]-ac_cnts[l-1])

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

int main(){
  int A,B,C;
  cin>>A>>B>>C;
  int K;
  cin>>K;
  int max_num=max(A,max(B,C));
  int remain=A+B+C-max_num;
  cout<<remain+max_num*pow(2,K)<<endl;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

//-----------------------------------------------------------------------------

struct BinaryIndexedTree {
	int bit[200010] = {},n;
	BinaryIndexedTree(int N):n(N) {}
	int sum(int i) {
		int s=0;
		while(i>0) s+=bit[i],i-=i&-i;
		return s;
	}
	void add(int i,int x) {
		while(i<=n) bit[i]+=x,i+=i&-i;
	}
};

int n;
ll k,a[200010],sum[200010];
vector<P> vec;
ll ans;

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

	cin>>n>>k;
	REP(i,n) {
		cin>>a[i];
		sum[i+1]=sum[i]+a[i]-k;
		vec.pb(P(sum[i+1],i+2));
	}
	vec.pb(P(0,1));
	sort(ALL(vec));
	BinaryIndexedTree tree(n+1);
	for(auto v:vec) {
		ans+=tree.sum(v.se);
		tree.add(v.se,1);
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 8560
#include <bits/stdc++.h>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)(x).size())
#define mset(a,v) memset(a,v,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
#define MOD 1000000007
using namespace std;
typedef long long ll;

int n,m;ll z,s;
vector<pair<int,ll> > g[200005];
pair<ll,pair<int,int> > e[200005];
int f[18][200005];
ll w[18][200005];
int d[200005];
int uf[200005];

int find(int x){
	if(uf[x]<0)return x;
	return uf[x]=find(uf[x]);
}
bool join(int x, int y){
	x=find(x);y=find(y);
	if(x==y)return false;
	if(uf[x]>uf[y])swap(x,y);
	uf[x]+=uf[y];
	uf[y]=x;
	return true;
}

void dfs(int x, int pa){
	for(auto p:g[x]){
		int y=p.fst;ll c=p.snd;
		if(y==pa)continue;
		f[0][y]=x;
		w[0][y]=c;
		d[y]=d[x]+1;
		dfs(y,x);
	}
}

ll query(int x, int y){
	assert(x!=y);
	if(d[x]<d[y])swap(x,y);
	ll r=-1;
	for(int k=17;k>=0;--k)if(d[x]-(1<<k)>=d[y]){
		r=max(r,w[k][x]);
		x=f[k][x];
	}
	assert(d[x]==d[y]);
	if(x==y)return r;
	for(int k=17;k>=0;--k)if(f[k][x]!=f[k][y]){
		r=max(r,max(w[k][x],w[k][y]));
		x=f[k][x];y=f[k][y];
	}
	assert(x!=y&&f[0][x]==f[0][y]);
	return max(r,max(w[0][x],w[0][y]));
}

ll a[200005];
ll p2[200005];

int main(){
	mset(uf,-1);
	p2[0]=1;
	fore(i,1,200005)p2[i]=(2*p2[i-1])%MOD;
	scanf("%d%d%lld",&n,&m,&z);
	fore(i,0,m){
		int x,y;ll c;
		scanf("%d%d%lld",&x,&y,&c);x--;y--;
		e[i]=mp(c,mp(x,y));
	}
	sort(e,e+m);
	fore(i,0,m){
		int x=e[i].snd.fst,y=e[i].snd.snd;ll c=e[i].fst;
		x=find(x);y=find(y);
		if(join(x,y)){
			s+=c;
			g[x].pb(mp(y,c));
			g[y].pb(mp(x,c));
		}
	}
	f[0][0]=-1;dfs(0,-1);
	fore(k,1,18)fore(i,0,n){
		if(f[k-1][i]<0)f[k][i]=-1,w[k][i]=w[k-1][i];
		else {
			f[k][i]=f[k-1][f[k-1][i]];
			w[k][i]=max(w[k-1][i],w[k-1][f[k-1][i]]);
		}
	}
	fore(i,0,m){
		int x=e[i].snd.fst,y=e[i].snd.snd;ll c=e[i].fst;
		a[i]=s-query(x,y)+c;
	}
	sort(a,a+m);
	int i=lower_bound(a,a+m,z)-a;
	int j=upper_bound(a,a+m,z)-a;
	ll r;
	if(i==j)r=0;
	else if(i)r=2*(p2[j-i]-1)%MOD*p2[m-j]%MOD;
	else r=(p2[j-i]+MOD-2)%MOD*p2[m-j]%MOD;
	printf("%lld\n",r);
	return 0;
}

Measured memory_bytes: 52480
N, A, B = map(int, input().split())

if (A > B):
    print(0)
    exit()
elif (B > A and N == 1):
    print(0)
    exit()
elif (A == B and N == 1):
    print(1)
    exit()
else:
    ma = B * (N - 2)
    mi = A * (N - 2)
    print(ma - mi + 1)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define double long double
#define int long long
#define mii map<int,int>
#define pii pair<int,int>
#define low lower_bound
#define upp upper_bound
#define mod 1000000007 //10^9+7
#define inf (int)50000000000 //5･10^10
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define F first
#define S second
using namespace std;
signed main() {
  int n,m;
  cin>>n>>m;
  vector<int>st,go;
  rep(i,m) {
    int a,b;
    cin>>a>>b;
    if(a==1) st.push_back(b);
    else if(b==n) go.push_back(a);
  }
  vsort(st);
  vsort(go);
  rep(i,st.size()) {
    if(bisea(all(go),st[i])) {
      cout<<"POSSIBLE"<<endl;
      return 0;
    }
  }
  cout<<"IMPOSSIBLE"<<endl;
}

Measured memory_bytes: 1984
N = int(input())

Ans = [0] * (N+1)
Ans[0] = 2
Ans[1] = 1
hantei = [False] * (N+1)
hantei[0] = True
hantei[1] = True

def fib(n):
    if hantei[n]:
        return Ans[n]
    else:
        Ans[n] = fib(n-1) + fib(n-2)
        hantei[n] = True
        return Ans[n]

print(fib(N))


Measured memory_bytes: 3060
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

const int maxn = 1e5 + 10;
pair<ll, ll> p[maxn];
ll par[maxn];
ll s[maxn];
ll sum;
ll ans[maxn];
ll find(ll x) { return par[x] == x ? x : par[x] = find(par[x]); }

int main() {
    ll n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        s[i] = 1;
    }
    for (int i = 0; i < m; i++) {
        scanf("%lld%lld", &p[i].first, &p[i].second);
    }
    sum = 1LL * n * (n - 1) / 2;
    for (int i = m - 1; i >= 0; i--) {
        ans[i] = sum;
        int x = find(p[i].first), y = find(p[i].second);
        if (x != y) {
            par[y] = x;
            sum -= s[x] * s[y];
            s[x] += s[y];
        }
    }
    for (int i = 0; i < m; i++) printf("%lld\n", ans[i]);
    return 0;
}


Measured memory_bytes: 5120
s = input()

ccount = 0;
i = 0

for c in s:
    if i == 0:
        if c != "A":
            print("WA")
            exit()
    elif 2 <= i and i <= len(s) - 2 and c == "C":
        if ccount >= 1:
            print("WA")
            exit()
        ccount = ccount + 1
    else:
        if c.isupper():
            print("WA")
            exit()
    i += 1

print("AC" if ccount == 1 else "WA")

Measured memory_bytes: 3064
import bisect
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
color_list = [1, 400, 800, 1200, 1600, 2000, 2400, 2800, 3200]
color_dict = defaultdict(int)
red_count = 0
for i in a:
  idx = bisect.bisect_right(color_list, i)
  if 1 <= idx <= 8:
    color_dict[idx] += 1
  elif idx == 9:
    red_count += 1
if len(color_dict) >= 1:
  print(len(color_dict), len(color_dict)+red_count)
else:
  print(1, red_count)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    ll n, m, ans = 0; cin >> n >> m;
    priority_queue<ll> que;
    vector<pair<ll, ll>> cng(m);
    rep(i, n){ ll a; cin >> a; que.push(-a); }
    rep(i, m) cin >> cng[i].second >> cng[i].first, cng[i].first *= -1;
    sort(all(cng));
    rep(i, m){
        bool exit = false;
        rep(j, cng[i].second){
            if(-que.top()<-cng[i].first){ que.pop(); que.push(cng[i].first); }
            else{ exit = true; break; }
        }
        if(exit) break;
    }
    while(!que.empty()){ ans += -que.top(); que.pop(); }
    cout << ans << endl;
}

Measured memory_bytes: 2936
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1e+9+7 //10^9+7
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>=(ll)(b);i--)

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//グローバル変数

//ライブラリ挿入

int main(){
    //入力
    int N,M;
    cin >> N >> M;
    vector<vector<pair<int,ll>>> dist(N);
    vector<ll> x(N,INF);
    int l,r;
    ll d;
    REP(i,M){
        cin >> l >> r >> d;
        l--;
        r--;
        dist[l].push_back({r,d});
        dist[r].push_back({l,-d});
    }

    //処理
    bool flag=true;
    vector<bool> visited(N,false);
    int cur,next;
    ll x_next;
    queue<int> que;
    REP(i,N){
        if(visited[i]) continue;
        x[i]=0;
        visited[i]=true;
        que.push(i);
        while(!que.empty()){
            cur=que.front();
            que.pop();
            
            REP(j,dist[cur].size()){
                next=dist[cur][j].first;
                x_next=x[cur]+dist[cur][j].second;
                if(!visited[next]){
                    visited[next]=true;
                    x[next]=x_next;              
                    que.push(next);
                }
                if(x[next]!=x_next) flag=false;
                if(!flag) break;
            }
            if(!flag) break;
        }
        if(!flag) break;

    }

    //答え
    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

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

int main()
{
    long long t,i,j,k,n,c=0;
    string s;
    cin>>s;
    if(s[0]=='R'&&s[1]=='R'&&s[2]=='R') cout<<"3"<<endl;
    else if(s[0]=='R'&&s[1]=='S'&&s[2]=='R')cout<<"1"<<endl;
    else if(s[0]=='R'&&s[1]=='R'&&s[2]=='S')cout<<"2"<<endl;
    else if(s[0]=='R'&&s[1]=='S'&&s[2]=='S')cout<<"1"<<endl;
    else if(s[0]=='S'&&s[1]=='R'&&s[2]=='R')cout<<"2"<<endl;
    else if(s[0]=='S'&&s[1]=='S'&&s[2]=='R')cout<<"1"<<endl;
    else if(s[0]=='S'&&s[1]=='R'&&s[2]=='S')cout<<"1"<<endl;
    else if(s[0]=='S'&&s[1]=='S'&&s[2]=='S')cout<<"0"<<endl;


    return 0;
}


Measured memory_bytes: 3592
import sys
from bisect import bisect, bisect_left

input = sys.stdin.readline
N = int(input())
L = sorted([int(x) for x in input().split()])
c = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        f = bisect_left(L, L[i] + L[j])
        c += f - j - 1
print(c)

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

int main()
{
    int n,q;
    int a,v;
    int array[1000001]={};
    int index, max_num;
    cin >> n >> q;
    index = n+1;
    max_num = 0;

    while(cin >> a >> v)
    {
        array[a] +=v;
        if(v>0)
        {
            if((array[a] > max_num) || ((array[a] == max_num) && a < index))
            {
                index = a;
                max_num = array[a];                
            }
        }
        else
        {
            if(a == index)
            {
                index = n+1;
                max_num = 0;
                for(int i=1; i<=n; i++)
                {
                    if(array[i] > max_num)
                    {
                        index = i;
                        max_num = array[i];
                    }
                }
            }
        }
        cout << index << " " << max_num << endl;
    }
    return 0;
}

Measured memory_bytes: 7008