akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector< pair<int, int> > vpii;
#define MOD 1000000007
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define rep(i, a, b) for (int i = a; i < b; i++)
#define input_arr(a, n)         \
    for (int i = 0; i < n; i++) \
        cin >> a[i];
#define print_arr(a, n)         \
    for (int i = 0; i < n; i++) \
        cout << a[i] << " ";
#define deb(n) cerr << #n << "=" << n << "\n";

void fst() {
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

bool isTriangle(int a, int b, int c) {
    if((a+b > c) && (b+c > a) && (a+c > b))
        return 1;
    return 0;
}

bool allDiff(int a, int b, int c) {
    if(a != b && b!=c && a!=c)
        return 1;
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vi arr(n);
    input_arr(arr, n);
    int ans = 0;
    FOR(i, n - 2)
    {
        rep(j, i + 1, n-1) {
            rep(k, j + 1, n) {
                if(allDiff(arr[i], arr[j], arr[k]) && isTriangle(arr[i], arr[j], arr[k]))
                    ans++;
            }
        }
    }
    cout << ans;
}

int main() {
    fst();
    solve();
    return 0;
}


Measured memory_bytes: 3628
N = int(input())
B = list(map(int,input().split()))
A = [0]*N

for i in range(N-1,-1,-1):
    if i == N-1:
        A[i] = B[i-1]
    elif i == 0:
        A[i] = B[0]
    else:
        A[i] = min(B[i],B[i-1])
print(sum(A))

Measured memory_bytes: 3060
int main() {
  double n, k, a[100002], min = 100001, ans;
  
  scanf("%lf %lf", &n, &k);
  
  for(int i = 0; i < n; i++) {
    scanf("%lf", &a[i]);
  }
  
  ans = (n - 1) / (k - 1) + 0.9999999999;
  
  printf("%d", (int)ans);
 
  return 0;
}

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

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

  vector<int> vec(N + 1, -1);
  vec.at(0) = 1;
  vec.at(1) = 1;

  for (int i = 0; i < M; i++) {
    cin >> A;
    vec.at(A) = 0;
  }

  for (int i = 2; i < N + 1; i++) {
    if (vec.at(i) != 0) vec.at(i) = (vec.at(i - 2) + vec.at(i - 1)) % 1000000007;
  }

  cout << vec.at(N) << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; i++)
#define rep2(i,a,n) for (int i = a; i < n; i++)
using namespace std;
int H, W;
int C[10][10];
int A[201][201];

void init() {
    cin >> H >> W;
    rep(i, 10) rep(j, 10) {
        int c; cin >> c;
        C[i][j] = c;
    }
    rep(h, H) rep(w, W) {
        int a; cin >> a;
        A[h][w] = a;
    }

}

void solve() {
    int res = 0;;

    for (int k = 0; k < 10; k++) rep(i, 10) rep(j, 10) {
        C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
    }

    rep(h, H) {
        rep (w, W) {
            if (A[h][w] == -1) continue;
            int from = A[h][w];
            res += C[from][1];
        }
    }


    printf("%d\n", res);
}

int main() {
    init();
    solve();
    return 0;
}


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

const int INF = 1001001001;

int main() {
  int a, b, c;
  cin >> a >> b >> c;

  if((a > c && c > b) || (b > c && c > a)) cout << "Yes" << endl;
  else cout<<"No"<<endl;

  return 0;
}

Measured memory_bytes: 256
c11,c12,c13=map(int,input().split())
c21,c22,c23=map(int,input().split())
c31,c32,c33=map(int,input().split())

if c21-c11==c22-c12 and c23-c13==c21-c11 and c31-c21==c32-c22 and c33-c23 ==c31-c21 and c12-c11==c22-c21 and c32-c31==c22-c21 and c33-c32==c23-c22 and c23-c22==c13-c12:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include <iostream>
#include <cmath>

bool solve(int a, int b, int c) {
  int64_t cur = c - a - b;
  return cur > 0 && ((int64_t)4 * a * b < cur * cur);
}

int main() {
  int a, b, c;
  std::cin >> a >> b >> c;
  if (solve(a, b, c)) std::cout << "Yes" << std::endl;
  else std::cout << "No" << std::endl;
  return 0;
}


Measured memory_bytes: 256
while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
   
    result = 0
    for a in range(1, x // 3):
        for b in range(a + 1,  x // 2):
            c = x - a - b
            if b < c <= n:
                result += 1    
    print(result)

Measured memory_bytes: 7560
//
//  main.cpp
//  abc086
//
//  Created by 吉川太陽 on 2019/12/19.
//  Copyright © 2019 Taiyo Kikkawa. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;


int main(int argc, const char * argv[]) {
    
    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N, Y;
    cin >> N >> Y;
    
    int man,gosen,sen;
    man=-1;
    gosen=-1;
    sen=-1;
    
    int i,j,k;
    bool found = false;
    
    for(i=0;i<=N;i++){
        for(j=0;i+j<=N;j++){
            k=N-i-j;
            if(10000*i+5000*j+1000*k == Y){
                man=i;
                gosen=j;
                sen=k;
                found = true;
                break;
            }
            if(found)
                break;
        }
        if(found)
            break;
    }
    
    cout << man << " " << gosen << " " << sen << endl;
    
    return 0;
}


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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod =(1e9)+7;
using P = pair<ll,ll>;

int main(){
    ll n,r;cin >>n>>r;
    ll ans;
    ans=n>10?r:r+100*(10-n);
    cout <<ans <<endl;
    return 0;
}



Measured memory_bytes: 256
c = [list(map(int, input().split())) for i in range(3)]
for i in range(3):
    for j in range(3):
        for k in range(3):
            for l in range(3):
                if c[i][j] + c[k][l] != c[i][l] + c[k][j]:
                    print('No')
                    exit()
print('Yes')


Measured memory_bytes: 61300
n=int(input())
a=list(map(int, input().split()))
ng = False
for num in a:
  if num % 2 == 0:
    if num % 3 == 0 or num % 5 == 0:
      continue
    else:
      ng = True
      break

if not ng:
  print("APPROVED")
else:
  print("DENIED")

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define ll signed long long int
#define MAXX 1000005
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
 
 
signed main()
{
	FAST;
	ll n, m = 0, a, b, c;
	cin >> n;
	for( a = 1;a <= n; a++){
			for( b = 1; b <= n; b++){
			
			for( c = 1; c <= n; c++){

		     	m += __gcd(__gcd(a,b), c);
		
		     
			}
		}
			
		}
		cout << m;
		}
		
		
	
	


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

void print(vector<string>& A) {
  cout << A[0];
  for (int i = 1; i < A.size(); i++) {
    cout << ' ' << A[i];
  }
  cout << endl;
}

void bubble_sort(vector<string>& A) {
  int N = A.size();
  for (int i = 0; i < N; i++) {
    for (int j = N-1; i < j; j--) {
      if (A[j][1] < A[j-1][1]) swap(A[j], A[j-1]);
    }
  }
}

void selection_sort(vector<string>& A) {
  int N = A.size();
  for (int i = 0; i < N; i++) {
    int minj = i;
    for (int j = i; j < N; j++) {
      if (A[j][1] < A[minj][1]) minj = j;
    }
    if (i != minj) swap(A[i], A[minj]);
  }
}

int main() {
  int N;
  cin >> N;
  vector<string> A(N), B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    B[i] = A[i];
  }

  bubble_sort(A);
  print(A);
  cout << "Stable" << endl;

  selection_sort(B);
  print(B);
  for (int i = 0; i < N; i++) {
    if (A[i] != B[i]) {
      cout << "Not stable" << endl;
      exit(0);
    }
  }
  cout << "Stable" << endl;
}


Measured memory_bytes: 3180
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static final int[] weights = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while ((line = br.readLine()) != null) {
			int stuff = Integer.parseInt(line);
			StringBuilder sb = new StringBuilder();

			for (int i = 0; i < 10; i++) {
				if ((stuff & weights[i]) > 0) {
					sb.append(" " + weights[i]);
				}
			}
			System.out.println(sb.substring(1));
		}
	}
}

Measured memory_bytes: 16892
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n , m,k;
    cin>>n>>m>>k;
    bool answered = false;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(   i*m + j*n - 2*i*j == k)
            {
                cout<<"Yes";
                answered = true;
                break;
            }

        }
        if( answered )
            break;
    }
    if( !answered )
    {
        cout<<"No";
    }
}

Measured memory_bytes: 3604
macro_rules! get {
    (Vec<$t:ty>) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let N = get!(usize);

    println!("ABC{}", N);
}

Measured memory_bytes: 4352
import java.util.Scanner;

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

    int N = scanner.nextInt();
    int M = scanner.nextInt();

    int[][] edges = new int[M][2];
    int[][] graph = new int[N][N];
    for (int i = 0; i < M; i++) {
      int a = scanner.nextInt() - 1;
      int b = scanner.nextInt() - 1;
      graph[a][b] = 1;
      graph[b][a] = 1;
      edges[i][0] = a;
      edges[i][1] = b;
    }

    int count = 0;
    for (int i = 0; i < M; i++) {
      int[][] g = new int[N][N];
      for (int j = 0; j < N; j++) System.arraycopy(graph[j], 0, g[j], 0, N);
      int a = edges[i][0];
      int b = edges[i][1];
      g[a][b] = 0;
      g[b][a] = 0;

      boolean[] visited = new boolean[N];
      visited[0] = true;
      dfs(g, visited, N, 0);
      for (int j = 0; j < N; j++) {
        if (!visited[j]) {
          count++;
          break;
        }
      }
    }
    System.out.println(count);
  }

  private static void dfs(int[][] graph, boolean[] visited, int N, int i) {
    for (int j = 0; j < N; j++) {
      if (graph[i][j] > 0 && !visited[j]) {
        visited[j] = true;
        dfs(graph, visited, N, j);
      }
    }
  }
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for (int i = 0; i < (n); ++i)
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; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin >> n;
    int t=0,f=0;
    rep(i,n){
        int a;cin >> a;
        if(a%4==0){
            f++;
        }
        else if(a%2==0){
            t++;
        }
    }
    if(t){
        if(t+2*f>=n){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
    else{
        if(2*f+1>=n){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define NMIN 1
#define NMAX 100
#define AMIN 0
#define AMAX 100

int main(){
  int N,A[NMAX],i,flag=1,subA,cnt=0;
  scanf("%d",&N);
  if(N<NMIN||N>NMAX) exit(1);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
    if(A[i]<AMIN||A[i]>AMAX) exit(1);
  }
  
  while(flag){
    flag=0;
    for(i=N-1;i>=1;i--){
      if(A[i]<A[i-1]){
	subA=A[i];
	A[i]=A[i-1];
	A[i-1]=subA;
	cnt++;
	flag=1;
      }
    }
  }
   for(i=0;i<N;i++){
     if(i==N-1)
     printf("%d\n",A[i]);
     else
       printf("%d ",A[i]);
   }
  printf("%d\n",cnt);
  return 0;
}



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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

using namespace std;

template <typename T> T &chmin(T &a, const T &b) {return a = min(a, b);}
template <typename T> T &chmax(T &a, const T &b) {return a = max(a, b);}

using ll = long long;
using ld = long double;

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);

int main(){
  string s;
  int n, k;
  cin >> n >> k;
  cin >> s;
  s[--k]+=32;
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

const int MAX = 999999;
int Prime[MAX];

void makePrimeList(int n) {
  Prime[0] = 1;
  int i, j;
  for (i = 2; i <= n / 2; i++) {
    for (j = 2; i * j <= n; j++) {
      Prime[i * j - 1] = 1;
    }
  }
}

int isPrime(int n) {
  if (Prime[n - 1] == 0) return 1;
  return 0;
}

int main() {
  
  int n, i, cnt, oldMax = 0;
  
  int init;
  for (init = 0; init <= MAX; init++) { Prime[init] = 0; }
  
  while(1) {
    if (scanf("%d", &n) == EOF) break;
    
    if (oldMax < n) {
      makePrimeList(n);
      oldMax = n;
    }
    cnt = 0;
    
    for (i = 1; i <= n; i++) {
      if (isPrime(i) == 1) cnt++;
    }
    
    printf("%d\n", cnt);
  }
  return 0;
}

Measured memory_bytes: 0
a, v = map(int,input().split())
b, w = map(int,input().split())
t= int(input())

l = abs(b-a)
dv = v-w

if dv <= 0:
    print("NO")
else:
    if l == 0:
        print("YES")
    else:
        if dv*t >= l:
            print("YES")
        else:
            print("NO")
  

Measured memory_bytes: 9184
#include <cstdio>

using namespace std;

int main() {
    int n, k, h, cnt = 0;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &h);
        if (h >= k) ++cnt;
    }
    printf("%d\n", cnt);
    return 0;
}


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

int N;
ll a[100000];


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

	cin >> N;

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

	ll ans = 1LL << 60;
	for(int loop = 0; loop < 2; loop++) {
		ll sum = 0;
		ll x = 0;
		ll t = 1;
		if(loop == 1) t = -1;
		for(int i = 0; i < N; i++) {
			sum += a[i];
			if(t == 1 && sum <= t || t == -1 && sum >= t) {
				x += abs(t - sum);
				sum = t;
			}
			t *= -1;
		}
		ans = min(ans, x);
	}
	cout << ans << endl;
}

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

//-std=c++11
//#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define LL long long
#define FI ios_base::sync_with_stdio(0); cin.tie(NULL);
#define PREC cout << setprecision(10) << fixed;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 9;
const int MX = 1e5 + 5;

int main()
{
	int n;
	cin >> n;
	vector<int> d1(n), d2(n);
	int ans = 0;
	for(int i=0;i<n;i++) {
		cin >> d1[i] >> d2[i];

		if(i >= 2) {
			if(d1[i] == d2[i] && d1[i-1] == d2[i-1] && d1[i-2] == d2[i-2]) {
				ans = 1;
			}
		}
	}
	if(ans == 1) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector< vector<int> > VVI;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()


ll modpow(ll a,ll n,ll mod){
  ll res=1;
  while(n){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a,ll mod){
  return modpow(a,mod-2,mod);
}

const int MAX=510000;
const int MOD=1000000007;
ll fac[MAX],finv[MAX],inv[MAX];

void COMinit(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  rep(i,MAX){
    if(i>1){
      fac[i]=fac[i-1]*i%MOD;
      inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
      finv[i]=finv[i-1]*inv[i]%MOD;
    }
  }
}

ll COM(int n,int k){
  if(n<k) return 0;
  if(n<0||k<0) return 0;
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
 
int main(){
  int N,K;
  cin>>N>>K;
  COMinit();
  if(N-1<=K) cout<<COM(2*N-1,N-1)<<endl;
  else{
    ll ans=0;
    while(K>=1){
      ll X=COM(N,K)*COM(N-1,K)%MOD;
      ans=(ans+X)%MOD;
      K-=1;
    }
    ans++;
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 12160
v_num, e_num, r = map(int, input().split())
INF = (10000 + 1) * v_num
dist = [INF] * v_num
G = [[] for _ in range(v_num)]
for _ in range(e_num):
    s, t, d = tuple(map(int, input().split()))
    G[s].append((t, d))

from heapq import heappush, heappop
q = []
heappush(q, (0, r))
dist[r] = 0
while q:
    d, node = heappop(q)
    for to, cost in G[node]:
        if dist[to] > d + cost:
            dist[to] = d + cost
            heappush(q, (d+cost, to))

for d in dist:
    if d == INF:
        print('INF')
    else:
        print(d)




Measured memory_bytes: 90560
#include <cstdio>

const int MAXN = 15;
int a[MAXN], flag;

void dfs(int p, int b, int c)
{
    if(p == 10)
    {
        flag = 1;
        return;
    }
    if(a[p] > b) dfs(p + 1, a[p], c);
    if(a[p] > c) dfs(p + 1, b, a[p]);
}

int main()
{
    int t;
    while(~scanf("%d", &t))
    {
        while(t--)
        {
            flag = 0;
            for(int i = 0; i < 10; i++)
                scanf("%d", &a[i]);
            dfs(0, 0, 0);
            printf("%s\n", flag ? "YES" : "NO");
        }
    }
    return 0;
}

Measured memory_bytes: 1008
N, M , X, Y = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]
if X < Y and max(x) < min(y) and  min(y) > X and max(x) < Y:
    print('No War')
else:
    print('War')

Measured memory_bytes: 3060
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    ll x, k, d;
    cin >> x >> k >> d;
    x = abs(x);
    ll num = x / d;
    if (num > k) {
        cout << x - d * k << endl;
        return 0;
    }
    else {
        ll rest = k - num;
        x -= num * d;
        if (rest % 2 == 0) {
            cout << x << endl;
        }
        else {
            cout << abs(x - d) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#ifdef __DEBUG__
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const deque<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const set<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int N;
vector<pll> food;
void input(){
    fast_io();
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        ll a,b; cin >> a >> b;
        food.emplace_back(a,b);
    }
    
}

int solve(){
    sort(food.begin(),food.end(),[](pll a,pll b){return a.first+a.second>b.first+b.second;});
    ll ans = 0;
    for (int i = 0; i < N; i++)
    {
        if(i%2==0) ans+=food[i].first;
        else ans-=food[i].second;
    }
    cout << ans << endl;
    
    return 0;
}   

int main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 2420
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    readln;
    auto ws = readln.split.to!(int[]);
    int ret, l, r;
    foreach (w; ws) r += w;
    ret = abs(l-r);
    foreach (w; ws) {
        r -= w;
        l += w;
        ret = min(ret, abs(l-r));
    }
    writeln(ret);
}

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

const string YES = "Yes";
const string NO = "No";

void solve(std::string S)
{
    bool isAnagram = (S == "abc" || S == "acb" || S == "bac" || S == "bca" || S == "cab" || S == "cba");
    cout << (isAnagram ? YES : NO) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


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

using namespace std;

int main(){
	int p[110][110], W, H, N;
	int x, y, a;

	cin >> W >> H >> N;

	for (int j = 0; j < W; j++){
		for (int k = 0; k < H; k++){
			p[j][k] = 0;
		}
	}

	for (int i = 0; i < N; i++){
		cin >> x >> y >> a;

		if (a == 1){
			for (int j = 0; j < x; j++){
				for (int k = 0; k < H; k++){
					p[j][k] = 1;
				}
			}
		}
		if (a == 2){
			for (int j = x; j < W; j++){
				for (int k = 0; k < H; k++){
					p[j][k] = 1;
				}
			}
		}
		if (a == 3){
			for (int j = 0; j < W; j++){
				for (int k = 0; k < y; k++){
					p[j][k] = 1;
				}
			}
		}
		if (a == 4){
			for (int j = 0; j < W; j++){
				for (int k = y; k < H; k++){
					p[j][k] = 1;
				}
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < W; i++){
		for (int j = 0; j < H; j++){
			if (p[i][j] == 0) ans++;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
def insertionSort(A, N, g):
    global cnt
    for i in range(g, N):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
            #print('cnt = ' + str(cnt))
        A[j+g] = v

N = int(input())
A = [int(input()) for i in range(N)]
cnt = 0
G = []
h = 1
while (True):
	if h > N:
		break
	G.append(h)
	h = 3 * h + 1
G.reverse()
m = len(G)
for i in range(m):
    insertionSort(A, N, G[i])
print(m)
print(*G)
print(cnt)
print(*A, sep='\n')


Measured memory_bytes: 53284
n, p = map(int, input().split())
l = []
ans = 1

for i in range(2, int(p**0.5) + 2):
    if p%i == 0:
        cnt = 0
        while p%i == 0:
            p /= i
            cnt += 1
        l.append([i, cnt])

if p != 1:
    l.append([p, 1])

for i, j in l:
    while j >= n:
        ans *= i
        j -= n

print(int(ans))

Measured memory_bytes: 9448
#include <iostream>
using namespace std;
int main(){
  int n,sum=0;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      sum+=a[i]*a[j];
    }
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
from collections import Counter

N,M,K = map(int,input().split())

fn = [1]*N
CD = [0]*K

par = list(range(N))

def root(x):
    S = set()
    S.add(x)
    y = x
    while True:
        if par[y] == y:
            for s in S:
                par[s] = y
            return y
        S.add(y)
        y = par[y]

def unite(x,y):
    rx = root(x)
    ry = root(y)
    par[rx] = ry

for _ in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    fn[A] += 1
    fn[B] += 1
    unite(A,B)
    
for _ in range(K):
    C,D = map(int,input().split())
    C -= 1
    D -= 1
    CD[_] = (C,D)

par = [root(x) for x in range(N)]
c = Counter(par)

RESULT = [(c[par[x]] - fn[x]) for x in range(N)]

for C,D in CD:
    if par[C] == par[D]:
        RESULT[C] -= 1
        RESULT[D] -= 1

print(*RESULT,sep=" ")

Measured memory_bytes: 84568
#include<iostream>
#include<string>
using namespace std;
int main(){
    int n,i;
    cin >>n;
    string a1,a2;
    int t=0,h=0;
    
    for(i=0;i<n;i++){
        cin >>a1 >>a2;
        if(a1.compare(a2)==0){
            t++;h++;
        }else if(a1.compare(a2)>0) t+=3;
        else h+=3;
    }
    cout << t << " " << h << endl;
    return 0;
}


Measured memory_bytes: 3144
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

const int MAXN = 16;
const int INF = 100000;
string S[MAXN];
int dp[MAXN][1<<MAXN];
int memo[MAXN][MAXN][22];
int N;

int dfs(int now, int state) {
    int& ret = dp[now][state];
    if (ret >= 0) return ret;
    if (state == (1<<N)-1) return ret = 0;
    ret = INF;
    int sz = S[now].size();
    for (int i = 0; i < N; i++) if (((state>>i)&1) == 0) {
        int isz = S[i].size();
        for (int j = max(0, sz+1-isz); j <= sz; j++) {
            int ok = memo[now][i][j];
            if (ok) {
                int nstate = state|ok;
                ret = min<int>(ret, (isz-(sz-j)) + dfs(i, nstate));
            }
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (cin >> N) {
        if (N==0) break;
        for (int i = 0; i < N; i++)
            cin >> S[i];
        int ans = INF;
        memset(dp, -1, sizeof(dp));
        memset(memo, 0, sizeof(memo));
        for (int n = 0; n < N; n++) {
            int sz = S[n].size();
            for (int i = 0; i < N; i++) {
                int isz = S[i].size();
                for (int j = max(0, sz+1-isz); j <= sz; j++) {
                    const string s = S[n].substr(j);
                    const string t = S[i].substr(0, s.size());
                    if (s == t) {
                        const string u = s+S[i].substr(t.size());
                        int& ok = memo[n][i][j];
                        for (int k = 0; k < N; k++) {
                            if (u.find(S[k]) != string::npos) ok |= 1<<k;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            int state = 0;
            const string u = S[i];
            for (int j = 0; j < N; j++) {
                if (u.find(S[j]) != string::npos) state |= 1<<j;
            }
            ans = min<int>(ans, S[i].size() + dfs(i, state));
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 7244
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, int> > f;
long long n, ans = 1;
void dfs(long long x, int i){
    if(i == f.size()){
        if(x > sqrt(n) && n%x == 1) ans++;
        return;
    }
    for(int j=0;j<=f[i].second;j++){
        dfs(x, i+1);
        x *= f[i].first;
    }
}
int main(){
    scanf("%lld", &n);
    if(n == 2) printf("1\n");
    else{
        long long X = sqrt(n);
        for(long long i=2;i<=X;i++){
            long long x = n;
            while(x%i == 0) x/=i;
            if(x%i == 0 || x%i == 1) ans++;
        }
        long long last = n-1;
        long long m = last;
        for(long long i=2;i*i<=last;i++){
            int cnt = 0;
            while(m%i == 0) cnt++, m /= i;
            if(cnt != 0) f.emplace_back(make_pair(i, cnt));
        }
        if(m > 1) f.emplace_back(make_pair(m, 1));
        sort(f.begin(), f.end());
        dfs(1, 0);
        printf("%lld\n", ans);
    }
}

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

using namespace std;

long long N, M, ans;

int main(){
	cin >> N >> M;
	if(N == 1 && M == 1) ans = 1;
	else if(N == 1) ans = M - 2;
	else if(M == 1) ans = N - 2;
	else ans = (N - 2) * (M - 2);
	cout << ans << endl;
}

Measured memory_bytes: 256
def binarySearch(A, key, n):
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False

n = int(input())
S = tuple(map(int, input().split(' ')))

q = input()
T = tuple(map(int, input().split(' ')))

cnt = 0

for i in T:
    if binarySearch(S, i, n):
        cnt += 1

print(cnt)

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

#define INF 10000000

bool foo(int x){
  
}

int main(){
  long long int N, sq, ans = INF;

  cin>>N;

  for(long long int i = 1; i*i <= N; i++){
    if(N%i==0){
      long long temp = min(log10(N)+1,log10(N/i)+1);
      ans  = min(ans, temp);
    }
  }
  
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <vector>

typedef struct Node
{
    int id;
    int depth;
    Node *parent;
    std::vector<struct Node *> child;
} Node;

void set_depth_iter(Node &node, int depth){
    node.depth = depth;
    if(node.child.empty()) return;
    for(auto &x : node.child){
        set_depth_iter(*x, depth + 1);
    }
}

void set_depth(std::vector<Node> &nodes){
    Node root;
    for(auto &x : nodes){
        if(x.parent == nullptr){
            root = x;
            break;
        }
    }
    set_depth_iter(root, 0);
}

int main(){
    int n;
    std::scanf("%d", &n);
    std::vector<Node> nodes;
    for(int i = 0; i < n; ++i){
        Node node;
        node.id = i;
        node.depth = 0;
        node.parent = nullptr;
        node.child.clear();
        nodes.push_back(node);
    }

    for(int i = 0; i < n; ++i){
        int id;
        int num;
        std::scanf("%d", &id);
        std::scanf("%d", &num);
        for(int j = 0; j < num; ++j){
            int c;
            std::scanf("%d", &c);
            nodes[c].parent = &nodes[id];
            nodes[id].child.push_back(&nodes[c]);
        }
    }
    set_depth(nodes);

    for(int i = 0; i < n; ++i){
        int p = -1;
        if(nodes[i].parent != nullptr){
            p = nodes[i].parent->id;
        }

        int d = nodes[i].depth;
        std::printf("node %d: parent = %d, depth = %d, ", i, p, d);
        if(p == -1) std::printf("root, ");
        else if(nodes[i].child.empty()) std::printf("leaf, ");
        else std::printf("internal node, ");
        std::printf("[");
        for(auto iter = nodes[i].child.begin(); iter != nodes[i].child.end(); ++iter){
            std::printf("%d", (*iter)->id);
            if(*iter != *nodes[i].child.rbegin()){
                std::printf(", ");
            }
        }
        std::printf("]\n");
    }

    return 0;
}



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

int main(){

	for (int i = 1; i <= 9; ++i)
	{
		for (int j = 1; j <= 9; ++j)
		{
			cout << i << "x" << j << "=" << i * j << endl; 
		}
	}
    return 0;
}

Measured memory_bytes: 1112
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, K;

void solve() {
	cin >> N >> K;
	int s = (N - 1) * (N - 2) / 2 - K;
	if(s < 0) {
		cout << -1 << "\n";
	}
	else {
		cout << N - 1 + s << "\n";
		rep(i, 0, N - 1) {
			cout << i + 1 << " " << N << "\n";
		}
		rep(i, 0, N - 1) {
			rep(j, i + 1, N - 1) {
				if(s) {
					s--;
					cout << i + 1 << " " << j + 1 << "\n";
				}
			}
		}
	}
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())


long long c[100001];


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

	int n;
	long long k;
	cin>>n>>k;
	rep(i,n){
		int a,b;
		cin>>a>>b;
		c[a]+=b;
	}
	k--;
	rep(i,100001){
		if (k < c[i]){
			cout<<i<<endl;
			break;
		}
		k -= c[i];
	}

	return 0;
}

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

const int MAX_N=50;

int main() {
    int N;
    int A[MAX_N];
    int B[MAX_N];
    int C[MAX_N];

    cin>>N;
    rep(i,N)    cin>>A[i];
    rep(i,N)    cin>>B[i];
    rep(i,N-1)    cin>>C[i];

    int sum=0;

    rep(i,N) {
        sum=sum+B[(A[i]-1)];
        if(A[i]-1==A[i-1]&&i>0) {
            sum=sum+C[(A[i-1]-1)];
        }
    }
    cout<<sum;

 return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  if(k == 0){
    cout << (ll)n*n << endl;
    return 0;
  }
  ll ans = 0;
  rep2(b, k+1, n+1){
    ll add = b-k;
    add *= (n+1)/b;
    int m = (n+1) % b;
    // cerr << b << " " << add << " " << m << " " << m - k << endl;
    ans += add;
    if(m - k > 0) ans += (m-k);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>    //super header :標準ライブラリ,STLを全てインクルード
using namespace std;

int main(){
    int a,b,k;cin >> a >> b >> k;

    int cnt = 0;
    for(int i = min(a,b); i > 0; --i)
    {
        if(a%i+b%i==0){
            cnt++;
            if(cnt==k){
                cout << i << endl;
                break;
            } 
        }
    }
}


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

int main(){
	ll H,N;
	cin >> H >> N;
	vector<ll> A(N);
	vector<ll> B(N);
	rep(i,N){
		cin >> A[i] >> B[i];
	}
	
	vector<vector<long long>> dp(N+1, vector<long long>(H+1, INF));
	
	dp[0][0] = 0;
	
	rep(i,N){
		rep(j,H+1){
			dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
			dp[i+1][min(H,j+A[i])] = min(dp[i+1][min(H,j+A[i])], dp[i+1][j]+B[i]);
		}
	}
	
	cout << dp[N][H] << endl;
	
}



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

typedef long long ll;

ll n, k, c[30];
set<string> wow;

bool cmp(int a, int b) {
	return a > b;
}

int main() {

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

	memset(c, 0, sizeof(c));

	cin>>n>>k;

  	string a;
	for(ll i=0;i<n;i++) {
		cin>>a;
		if(wow.count(a) == 0) {
			wow.insert(a);
			c[a[0] - 'A']++;
		}
	}

	ll ans = 0;

	while(1) {
		sort(c, c+26, cmp);
		ll used = 0;
		for(ll i=0;i<26;i++) {
			if(c[i] > 0) {
				c[i]--;
				used++;
				if(used == k) break;
			}
		}
		if(used < k) break;
		else ans++;
	}

	cout<<ans<<endl;
}


Measured memory_bytes: 1152
#!/usr/bin/env python3
import sys


def solve(S: str):

    if S[len(S)-1]=="s":
        print(S+"es")
    else:
        print(S+"s")

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9104
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
#define N 100009
#define LL long long
#define INF 0x3f3f3f3f
#define mymin(x,y) (x>=y?y:x)
#define mymax(x,y) (x>=y?x:y)
int A[N], mark[N], mxt1[N];
multiset<int> mst;
int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	int n; cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> A[i];
	}
	multiset<int>::iterator iter;
	for(int i = n; i > 0; i--){
		if((iter = mst.upper_bound(A[i])) != mst.end()){
			mst.erase(iter);
		}
		mst.insert(A[i]);
	}
	cout << mst.size() << endl;
	return 0;
}


Measured memory_bytes: 8668
#include<bits/stdc++.h>
using namespace std;
#define MOD 2019
int main()
{
  long long l,r,minv;
  cin>>l>>r;
  minv=l*(l+1)%MOD;
  for(long long i=l; i<=r; i++){
    for(long long j=i+1; j<=r; j++){
      minv=min(minv,(i*j)%MOD);
      if(minv==0)break;   
    }
    if(minv==0)break;
  }
  cout<<minv<<'\n';
  return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define collect(arr, size) rep(i,size) cin >> arr[i];
#define int long long

struct lights{ int height = -1, width = -1;};
int H, W;
vector<string> fmap;
vector<vector<lights>> lmap;

bool is_within_map(int x, int y){
    return 0 <= x && x < W && 0 <= y && y < H;
}

void lamp_search(int x, int y){
    if(fmap[y][x]=='#') return;
    
    //search horizontally
    if(lmap[y][x].width == -1){
        int left = x, right = x;
        while(is_within_map(left-1, y)){
            if(fmap[y][left-1]=='#') break;
            left--;
        }
        while(is_within_map(right+1, y)){
            if(fmap[y][right+1]=='#') break;
            right++;
        }
        reps(i,left,right){
            lmap[y][i].width = right - left + 1;
        }
    }
    
    //search vertically
    if(lmap[y][x].height == -1){
        int top = y, bottom = y;
        while(is_within_map(x,bottom-1)){
            if(fmap[bottom-1][x]=='#') break;
            bottom--;
        }
        while(is_within_map(x,top+1)){
            if(fmap[top+1][x]=='#') break;
            top++;
        }
        reps(i,bottom,top){
            lmap[i][x].height = top - bottom + 1;
        }
    }
}

signed main(){
    cin >> H >> W;
    fmap = vector<string>(H);
    collect(fmap, H);
    lmap = vector<vector<lights>>(H,vector<lights>(W));
    
    rep(x,W)rep(y,H){
        lamp_search(x, y);
    }
    int maximum = -1;
    rep(x,W)rep(y,H){
        maximum = max(maximum, lmap[y][x].height+lmap[y][x].width-1);
    }
    cout << maximum << endl;
    return 0;
}

Measured memory_bytes: 66944
#include <bits/stdc++.h>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;

int x[100100];

int main()
{
    int n;
    cin >> n;
    ll sum = 0;
    rep(i, n) {
        int a;
        cin >> a;
        x[a]++;
        sum += a;
    }
    int q;
    cin >> q;
    rep(i, q) {
        int b, c;
        cin >> b >> c;
        sum = sum - (ll) x[b] * b + (ll) x[b] * c;
        cout << sum << endl;
        x[c] += x[b];
        x[b] = 0;
    }
    return 0;
}

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

int N;  vector<int> A;
const int MAX = 2000100;

int bit[MAX];

int sum(int a){ 
  int s = 0;
  while( a > 0 ){ s += bit[a]; a -= a & -a;}
  return s;
}

void add(int k, int x){
  
  while( k <= 2*N+100 ){
    bit[k] += x; 
    k += k & -k;
  }
  
}

signed main(void){ 
  
 
  cin >> N ;A.resize(N);
  
  for(int i = 0; i < N; i++){ cin >> A[i];}
  
  if( N == 1 ){ cout << A[0] << endl; return 0;}
  
  int M = (N*(N+1))/2;
  int judge;
  
  
  if( M % 2 == 0) { judge = M/2+1;}
  else{ judge = (M+1)/2;}
  
  
  
  
  
  int left = 0; int right = 1LL << 60; //ここ戻しとけ
  
  while( right - left > 1 ){ 
    
    int mid = left+(right-left)/2;
    
    vector<int> B(N);
    for(int i = 0; i < N; i++){ 
      if(A[i] >= mid ){ B[i] = 1;} else{ B[i] = -1;}
    }
    
    
    
    vector<int> S(N,0); S[0] = B[0];
    int cnt = 0;
    for(int i = 1; i < N; i++){ 
      S[i] = S[i-1]+B[i];
    }
    
   
    
    for(int i = 0; i < N; i++){ if( S[i] >= 0 ){ cnt++;} S[i] += N+1;} //単独の場合を記録
    
    
    
    for(int i = 0; i <= 2*N+100; i++){ bit[i] = 0;} //毎回初期化
    
    
    
    for(int i = 0; i < N; i++){ 
     
      cnt += sum(S[i]);
      add(S[i],1);
       
    }
    
   cnt = M-cnt;
    
    //この値が、部分列の中で中央値がmid以上のものの個数を表す
    
    if( cnt < judge ){ //midが十分小さい
      left = mid;
    }
    else{ //もっと攻められる
      right = mid;
    }
    
  }//while
  
  cout << left  << endl;
  
  return 0;
} 

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

int arr[10000001];
int dp[10000001];
    int n;

int solve(int idx)
{
    if(idx==n-1)
    {
        return 0;
    }
    if(dp[idx]!=-1) return dp[idx];
    int ans=solve(idx+1)+abs(arr[idx+1]-arr[idx]);
    if(idx+2<n) //check frog is on second last stone
    {
        ans=min(ans,solve(idx+2)+abs(arr[idx+2]-arr[idx]));

    }
    return dp[idx]=ans;
}
int main()
{
    memset(dp,-1,sizeof(dp));

    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    cout<<solve(0)<<endl;
}



Measured memory_bytes: 47816
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, t[1000000], m = 0, k;
    cin >> n;
    int a[n];
    for (int i = 0; i < 1000000; i++) t[i] = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        t[a[i]]++;
        t[a[i] + 1]++;
        t[a[i] + 2]++;
    }
    for (int i = 0; i < 1000000; i++)
        if (m < t[i]) m = t[i];
    cout << m;
}

Measured memory_bytes: 7888
n = int(input())
# i = 0
# 
# while i < n:
#     i = i + 1
#     if i % 3 == 0 or i % 10 == 3:
#         print(' ' + str(i),end='')
# 
# print()

s=""
for i in range(1,n+1):
    if i%3==0:
        s+=" "+str(i)
    elif "3" in list(str(i)):
        s+=" "+str(i)
print(s)

Measured memory_bytes: 7684
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC064B
{
    class Program
    {
        static void Main(string[] args)
        {
            int N;
            N = int.Parse(Console.ReadLine());
            int[] a = new int[N];
            string[] vals = Console.ReadLine().Split(' ');

            int min = int.MaxValue;
            int max = int.MinValue;

            for (int i = 0; i < N; i++)
            {
                a[i] = int.Parse(vals[i]);
                if (a[i] < min)
                    min = a[i];
                if (a[i] > max)
                    max = a[i];
            }

            Console.WriteLine(max - min);

        }
    }
}


Measured memory_bytes: 11092
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(){
  int n,h,a;
  int sum=0;
  scanf("%d %d",&h,&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a);
    sum+=a;
  }
  if(sum>=h){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long x[5]={0};
	for(long long i=0;i<5;i++){
		long long temp;
		cin>>temp;
		x[temp-1]++;
	}for(long long i=0;i<5;i++){
		if(x[i]==0){
			cout<<(i+1)<<endl;
			break;
		}
	}
	return 0;
}

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

int main() {
  int a, b;
  cin >> a >> b;

  if(a > b) {
    cout << "a" << " > " << "b" << endl;
  } else if(a == b) {
    cout << "a" << " == " << "b" << endl;
  } else {
    cout << "a" << " < " << "b" << endl;
  }
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
const int INF=1e9+5;
const int N=2e5+5;
const ll oo=1e18+5;
const ll mod=1e9+7;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	int sum=0;
	for(int i=0;i<m;++i){
		int x;
		cin>>x;
		sum+=x;
	}
	n-=sum;
	if(n<0) n=-1;
	cout<<n;
	return 0;
}


Measured memory_bytes: 3648
//
// Created by kuribohkute on 20/04/2019.
//
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define mp make_pair
#define X first
#define Y second
int main () {
    int n;
    cin >> n;
    vector <pair< int, int> > a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].Y >> a[i].X;
    }
    sort(a.begin(), a.end());
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i].Y;
        if (sum > a[i].X) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}


Measured memory_bytes: 1792