akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define rep(i,a,b) for(ll i = a;i <= b;i++)
#define repv(i,a,b) for(ll i = a;i >= b;i--)
#define e endl
#define all(v) v.begin(), v.end()
typedef pair<ll,ll> pp;

int lcm(int a, int b)
{
    int lar = max(a, b);
    int small = min(a, b);
    for (int i = lar; ; i += lar) {
        if (i % small == 0)
            return i;
    }
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b) {
    return (a.second < b.second);
}

ll power(ll x, unsigned ll y, ll p)
{
    ll res = 1;     // Initialize result
  
    x = x % p; // Update x if it is more than or
                // equal to p
   
    if (x == 0) return 0; // In case x is divisible by p;
  
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;
  
        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}

bool isPowerOfTwo (ll x)
{
    return x && (!(x&(x-1)));
} //cout << h[i] << " " << cnt[i] << " " << good[i] << " " << bad[i] << e;


void solve(){
    ll n; cin >> n;
    ll a[n];
    for(ll i = 0;i < n;i++){
        cin >> a[i];
    }
    sort(a, a+n);
    queue<ll> q;
    ll sum = 0;
    ll i = n-1;
    q.push(a[i]);
    i--;
    while(i >= 0){
        ll x = q.front();
        q.pop();
        sum += x;
        q.push(a[i]);
        q.push(a[i]);
        i--;
    }
    cout << sum << endl;
}
        
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //ll t; cin >> t; while(t--)
        solve();
}


Measured memory_bytes: 6380
(* O(n) *)
Scanf.scanf " %d %d %d" @@ fun w h n ->
  let left = ref 0 in
  let right = ref w in
  let down = ref 0 in
  let up = ref h in
  for i = 1 to n do
    Scanf.scanf " %d %d %d" @@ fun x y -> function
    | 1 -> left := max !left x
    | 2 -> right := min !right x
    | 3 -> down := max !down y
    | 4 -> up := min !up y
    | _ -> assert false
  done;
  let w2 = max 0 @@ !right - !left in
  let h2 = max 0 @@ !up - !down in
  Printf.printf "%d\n" @@ w2 * h2

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

int main() {
	//cout<<"GfG!";
	int x, y, c, t;
	cin>>x>>y;
	c = (4*x - y);  t = (y - 2 * x); 
    if (c % 2 == 0 && t % 2 == 0 && c >= 0 && t >= 0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
using namespace std;

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

	auto temp = a + b;
	if (temp % 2 != 0)
	{
		temp = temp / 2 + 1;
	}
	else
	{
		temp /= 2;
	}

	cout << temp << endl;

	return 0;
}


Measured memory_bytes: 256
n,x = map(int,input().split())
A = list(map(int,input().split()))

cnt = 0
for i in range(1,n):
    if A[i-1]+A[i] > x:
        cnt += A[i]-(x-A[i-1])
        A[i] = x-A[i-1]
        if A[i] < 0:
            A[i] = 0
            A[i-1] += A[i]

print(cnt)

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

int main() {
    using namespace std;

    int N, K;
    cin >> N >> K;

    int m = 1;
    for (int i=0; i<N; i++) {
        m = std::min(m*2, m+K);
    }

    cout << m << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long int

int main()
{
	io;
	ll n ;

	cin >> n ;

	ll amount = 0 , ct =0  ;

	while(amount < n ) { // 1000 < 19000
		amount += 1000; //
	}
	cout << amount - n ;
}

Measured memory_bytes: 3660
#include <stdio.h>

int main()
{
    int n;
    scanf("%d",&n);
    int cnt = 0;
    for(int i=1;i<=n;i+=2)
    {
        int t = 0;
        for(int j=1;j<=i;j++)
        {
            if(i%j==0) t++;
        }
        cnt += (t == 8);
    }
    printf("%d", cnt);
}

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

const int INF = 1001001001;
int n;
vector<int> to[1005];

vector<int> bfs(int sv){
  vector<int> dist(n, INF), pre(n, -1);
  queue<int> q;
  dist[sv] = 0;
  q.push(sv);
  while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int u : to[v]) {
      if (dist[u] != INF) continue;
      pre[u] = v;
      dist[u] = dist[v]+1;
      q.push(u);
    }
  }

  pair<int, int> best(INF, -1);
  rep(v, n) {
    if (v == sv) continue;
    for (int u : to[v]) {
      if (u == sv) {
        best = min(best, make_pair(dist[v],v));
      }
    }
  }
  if (best.first == INF) return vector<int>(n+1);
  int v = best.second;
  vector<int> res;
  while (v != -1){
    res.push_back(v);
    v = pre[v];
  }
  return res;
}

int main(){
  int m; cin >> n >> m;
  rep(i,m){
    int a,b; cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
  }

  vector<int> ans(n+1);
  rep(s, n) {
    vector<int> now = bfs(s);
    if (now.size() < ans.size()) ans = now;
  }
  if (ans.size() == n+1) {
    cout << -1 << endl;
    return 0;
  }
  cout << ans.size() << endl;
  for (int v : ans){
    cout << v+1 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main() {
  int h, n;
  cin >> h >> n;
  int sum = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    sum += a;
  }
  cout << (h > sum ? "No" : "Yes") << endl;
}

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

using namespace std;

#define all(x) (x).begin(),(x).end()

using ll = long long;
using P = pair<int,int>;
using mp =  map<int,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;

int n, k;
int a[200005];

bool check(int key) {
    int cnt = 0;
    for(int i = 0; i < n; ++i){
        cnt += (a[i] - 1) / key;
    }

    if (cnt <= k){
        return true;
    }else{
        return false;
    }
}

int main(void){

    cin >> n >> k;

    int amax = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        amax = max(a[i], amax);
    }

    int ng = 0, ok = amax, mid;
    while (abs(ok - ng) > 1) {
        mid = (ok + ng) / 2;

        if (check(mid)) ok = mid;
        else ng = mid;
    }

    cout << ok << "\n";

    return 0;
}


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

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);i++)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);i--)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
//constexpr long long MOD = 998244353LL;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

struct Edge {
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}


void solve(){
    ll n,k;
    cin>>n>>k;

    Matrix dp(62,Array(n,0));
    REP(i,n){
        cin>>dp[0][i];
        dp[0][i]--;
    }

    REP(i,61){
        REP(j,n){
            dp[i+1][j]=dp[i][dp[i][j]];
        }
    }

    ll now=0;
    REP(con,62){
        if((k>>con)&1){
            now = dp[con][now];
        }
    }
    cout<<now+1<<en;
}

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

    solve();
    //ll t;cin>>t;REP(i,t) solve();

    return 0;
}

Measured memory_bytes: 101676
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define N 200005
ll mod=998244353;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
ll powermodm(ll x,ll n,ll M){ll result=1;while(n>0){if(n % 2 ==1)result=(result * x)%M;x=(x*x)%M;n=n/2;}return result;}
ll power(ll _a,ll _b){ll _r=1;while(_b){if(_b%2==1)_r=(_r*_a);_b/=2;_a=(_a*_a);}return _r;}
ll gcd(ll a,ll b){while(a&&b)a>b?a%=b:b%=a;return a+b;}
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}
int main()
{
    fast;
    ll k,a,b;
    cin>>k>>a>>b;
    ll k1=k;
    k=k-a+1;
    ll x=k/2;
    ll x1=b+(x-1)*(b-a);
    if(k%2==1)
    {
        x1++;
    }
    cout<<max(k1+1,x1);
     return 0;
}


Measured memory_bytes: 256
n = int(input())

dp = [0]

l6 = []
l9 = []

for i in range(7):
    l6.append(6**i)
    l9.append(9**i)

for i in range(1, n+1):
    ans_i = []
    for j in range(7):
        if l6[j]<=i:
            ans_i.append(dp[i-l6[j]]+1)
        if l9[j]<=i:
            ans_i.append(dp[i-l9[j]]+1)
    dp.append(min(ans_i))

print(dp[n])

Measured memory_bytes: 3860
N,M = map(int, input().split())

A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

for i in range(N-M+1):
    for j in range(N-M+1):
        C = [A[k][i:i+M] for k in range(j, j+M)]
        if B == C:
            print('Yes')
            exit()

print('No')

Measured memory_bytes: 9200
import java.util.Scanner;

public class Main {

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

		String c = scan.nextLine();

		if (c.equals("a")) {
			System.out.println("vowel");

		} else if (c.equals("i")) {
			System.out.println("vowel");

		} else if (c.equals("u")) {
			System.out.println("vowel");

		} else if (c.equals("e")) {
			System.out.println("vowel");

		} else if (c.equals("o")) {
			System.out.println("vowel");

		} else {
			System.out.println("consonant");
		}

	}

}

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

#define mp make_pair
#define pb push_back
#define f first
#define s second 
#define sz(s) (int)s.size()
#define int long long
#define all(s) s.begin(), s.end()
#define forn(i, x, y) for(int i = x; i <= y; i++)
#define forev(i, y, x) for(int i = y; i >= x; i--)

using namespace std;

const int maxn = (int)3e5 + 100;
const int mod = (int)1e9 + 7;
const int P = (int)1e6 + 7;
const int inf = (int)1e9 + 7;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef long double ld;

string s;

main () {
  cin >> s;
  int ans = 0;
  while(1){
    int ok = 0, step=0;
    forn(i, 0, sz(s) - 1){
      if(s[i] == 'A') step++;
      else if(s[i] == 'B' && s[i + 1] == 'C')
        ans += step, i++;
      else
        step = 0;
    }
    cout<<ans;
    return 0;
  }
  cout << ans;
}

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

int main() {
	int n, m, g = 0;
	cin >> m >> n;
	int x[m][n], e[4][m * n];
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> x[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n - 1; j++) {
			if (x[i][j] % 2 == 1) {
				e[0][g] = i + 1;
				e[1][g] = j + 1;
				e[2][g] = i + 1;
				e[3][g] = j + 2;
				g++;
				x[i][j]--;
				x[i][j + 1]++;
			}
		}
		if (x[i][n - 1] % 2 == 1 && i < m - 1) {
			e[0][g] = i + 1;
			e[1][g] = n;
			e[2][g] = i + 2;
			e[3][g] = n;
			g++;
			x[i][n - 1]--;
			x[i + 1][n - 1]++;
		}
	}
	cout << g << endl;
	for (int i = 0; i < g; i++)cout << e[0][i] << " " << e[1][i] << " " << e[2][i] << " " << e[3][i] << endl;

	return 0;
}

Measured memory_bytes: 6912
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    int M;
    cin >> N;
    int i;
    vector<int> a;
    vector<int> b;
    vector<int> c;
    M=N;
    while(M--) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    M=N;
    while(M--) {
        int x;
        cin >> x;
        b.push_back(x);
    }
    M=N;
    while(M--) {
        int x;
        cin >> x;
        c.push_back(x);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    
    long g = 0;
    for(i=0;i<N;i++){
        auto itra = lower_bound(a.begin(), a.end(), b[i]);
        auto itrc = lower_bound(c.begin(), c.end(), b[i]+1);
        g+= (itra - a.begin()) *( c.end() - itrc);
    }
    cout << g << endl;
    return 0;
}


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

using namespace std;

const int MAXN = 1E5;
pair<long long, int> sushi[MAXN];
long long bestBal[MAXN + 1];

long long solve(int n, long long c, pair<long long, int> s[MAXN])
{
    bestBal[n] = 0;
    long long totalVal = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        totalVal += sushi[i].second;
        bestBal[i] = max(bestBal[i + 1], totalVal - (c - s[i].first));
    }
    long long ans = 0;
    totalVal = 0;
    for (int i = 0; i < n; i++)
    {
        totalVal += sushi[i].second;
        ans = max(ans, totalVal - sushi[i].first + max((long long) 0, bestBal[i + 1] - sushi[i].first));
    }
    return ans;
}

int main()
{
    int n;
    long long c;
    cin >> n >> c;
    for (int i = 0; i < n; i++)
    {
        cin >> sushi[i].first >> sushi[i].second;
    }
    long long ans = solve(n, c, sushi);
    for (int i = 0; i < n; i++)
        sushi[i].first = c - sushi[i].first;
    reverse(sushi, sushi + n);
    ans = max(ans, solve(n, c, sushi));
    cout << ans << endl;
    return 0;
}


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

int main() {
  int X,N;
  cin >> X >> N;
  vector<int> vec(102);
  
  if(N ==0){
    cout << X << endl;
    return 0;
  }
  
  for(int i =0; i < N;i++){
    int x;
    cin >> x;
    vec.at(x)=1;
  }
  pair<int, int> ans(99999, -1);
  
  for(int i=0; i < 102; i++){
    if(vec.at(i)==0){
      ans=min(ans,make_pair(abs(X-i),i));
    }
  }
  cout << ans.second <<endl;
}


Measured memory_bytes: 3624
import math
n=int(input())
x=math.ceil(math.sqrt(n*2))
if n==2:
    print(2)
    exit()
for i in range(x+1,0,-1):
    y=sum(range(i))
    if y<=n:
        s=list(range(1,i))
        t=n%y
        break
s=s[::-1]
for r in range(t):
    s[r]+=1
for h in s[::-1]:
    print(h)

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

using namespace std;
#define ll unsigned long long


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	ll W;
	cin>>n>>W;
	ll v[n], w[n];
	for (int i=0; i<n; i++){
		cin>>w[i]>>v[i];
	}
	ll dp[n+1][W+ 1];
	for (int i=0; i<=n; i++){
		for (int j=0; j<=W; j++){
			if(i == 0 || j == 0)	\
				dp[i][j] = 0;
			else if(j >= w[i - 1]) 
				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: 82424
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        
        int[] arr = new int[4];
        int n = scan.nextInt();
        
        while(n-- > 0){
            String temp = scan.next();
            switch(temp){
                case "G":
                    arr[0]++;
                    break;
                
                case "W":
                    arr[1]++;
                    break;
                    
                case "Y":
                    arr[2]++;
                    break;
                    
                case "P":
                    arr[3]++;
                    break;
            }
        }
        
        int ans = 0;
        for(int i : arr)
            if(i > 0) ans++;
            
        switch(ans){
            case 1:
                System.out.println("One");
                break;
                
            case 2:
                System.out.println("Two");
                break;
                
            case 3:
                System.out.println("Three");
                break;
                
            case 4:
                System.out.println("Four");
                break;
        }
        
    }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;cin>>S;
  string A="",B="";
  long d=1;
  long Q;cin>>Q;
  for(long q=0;q<Q;q++){
    long T;cin>>T;
    if(T==1)d*=-1;
    else{
      long F;char C;cin>>F>>C;
      if((F==1&&d==1)||(F==2&&d==-1))A+=C;
      else B+=C;
    }
  }
  reverse(A.begin(),A.end());
  string ans=A+S+B;
  if(d==-1)reverse(ans.begin(),ans.end());
  cout<<ans;
  
}

/*






*/

Measured memory_bytes: 1348
/*
        ####   ####
     ###    ###    ###
   ###    Bravery    ###
  ###  Determination  ###
   ##  Perseverance   ##
    ##   Integrity   ##
     ##  Patience   ##
      ## Kindness  ##
        ##Justice##
         ##     ##
           ## ##
             #
*/
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
typedef long long ll;
using namespace std;
int n,m,x,a[15][15],c[15],sum[15],mini=1000000000;
bool av;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>x;
	for (int i=0;i<n;i++){
		cin>>c[i];
		for (int j=0;j<m;j++) cin>>a[i][j];
	}
	for (int msk=0;msk<(1<<n);msk++){
		av=true;
		int cst=0;
		for (int i=0;i<m;i++) sum[i]=0;
		for (int i=0;i<n;i++){
			if ((1&(msk>>i))){
				cst+=c[i];
				for (int j=0;j<m;j++) sum[j]+=a[i][j];
			}
		}
		for (int i=0;i<m;i++) if (sum[i]<x) av=false;
		if (av) mini=min(mini,cst);
	}
	if (mini<1000000000) cout<<mini; else cout<<-1;
	return 0;
}

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

using namespace std;

int main(){
    int N,K;
    string S;
    cin >> N >> S >> K;

    char c = S[K - 1];

    for(int i = 0; i < N; i++){
        if( S[i] == c ) cout << S[i];
        else cout << "*";
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

vector<ll> v;

void dfs(ll val, int len){
    v.push_back(val);
    if(len == 10)   return;
    int i = val%10;
    for(int j = -1; j <= 1; j++){
        if(i+j < 0 || i+j > 9)  continue;
        dfs(val*10+i+j, len+1);
    }
}

int main(){
    int k;
    cin >> k;
    for(int i = 1; i <= 9; i++) dfs(i, 1);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    cout << v[k-1] << endl;
    return 0;
}

Measured memory_bytes: 5328
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N = I()

ans = INF
for n in range(1, int(math.sqrt(N))+1):
    if N % n == 0:
        ans = min(ans, int((n-1)+(N/n-1)))

print(ans)


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

signed main() {
  int n,k;
  cin>>n>>k;
  int ans = k;
  for(int i=0;i<n-1;++i) ans *= (k-1);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<queue>
#include<vector>
#define MA 10005
#define INF (1<<30)
using namespace std;
struct Node{
    short id;//根据题意，id最大在short有效范围内
    int weight;
};

short n;
vector<pair<int, int> >adj[MA];//加权有向图的邻接表
priority_queue<Node> PQ;//优先级队列
bool state[MA];//节点状态，false为未访问
int dis[MA];//节点到0点的权值总和

/**重载'<'以自定义优先级队列的优先级，这里定义为权值小优先，与默认的大优先相反*/
bool operator < (const Node node1, const Node node2){
    if(node1.weight==node2.weight)
        return node1.id > node2.id;//权值相同比id，意义不大
    return node1.weight > node2.weight;//返回与正常比较相反的结果
}

/**初始化*/
void init(){
    for(short i=0;i<n;i++)
        dis[i] = INF;//初始权值置为无穷
    dis[0] = 0;//0点权值为0
    Node ini;//0点
    ini.id=0;ini.weight = 0;//0点初始值
    PQ.push(ini);//将0点推入队列
}

/**狄克斯特拉算法*/
void dijkstra(){
    while(!PQ.empty()){//执行至队列为空
        Node nowNode = PQ.top();//从队列中取出元素
        PQ.pop();//清除取出的元素
        short nowId = nowNode.id;//当前元素的ID
        state[nowId] = true;//该节点已从队列中清除，设为访问完毕
        if(dis[nowId]>nowNode.weight)continue;//取出最小值，如果不是最短路径则忽略
        int nowSize = adj[nowId].size();//空间换时间，减少部分运算量
        for(int i=0; i<nowSize; i++){//遍历当前元素的邻接节点
            short nextId = adj[nowId][i].first;//下一个节点的ID
            if(state[nextId]) continue;//如果该节点已被读取则跳过
            int nextWeight = dis[nowId] + adj[nowId][i].second;//0到下一个节点的权值
            if(dis[nextId] > nextWeight){//发现了更短的路径
                dis[nextId] = nextWeight;//更新权值数组对应的数据
                Node nextNode;//即将推入队列的节点
                nextNode.id=nextId; nextNode.weight = nextWeight;//将数据存入节点
                PQ.push(nextNode);//将存有数据的节点推入队列
            }
        }
    }
}

int main(){
    int id, flag, nextId, weight;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&id, &flag);
        while(flag--){
            scanf("%d%d", &nextId, &weight);//读取邻接表
            adj[id].push_back(make_pair(nextId, weight));
        }
    }
    init();//执行初始化
    dijkstra();//执行狄克斯特拉算法
    for(short i=0;i<n;i++){//输出全部节点数据
        printf("%d %d\n", i, ((dis[i]==INF)?(-1):(dis[i])));
    }
    return 0;
}



Measured memory_bytes: 7620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++) 
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    //ll N; cin >> N;
    //ll N,M; cin >> N >> M;
    //string S; cin >> S;
    //ll H,W; cin >> H >> W;
    int N;
    cin >> N;
    string S;
    cin >> S;
    int left=0;
    int right=N/2+1;
    while(right-left>1){
        int mid=left+(right-left)/2;
        vector<pair<string,int>> happy;
        bool can=false;
        if(mid==0 || (mid==1 && N>26) || (mid==2 && N>1352))can=true;
        else{
            rep(i,N-mid+1){
                happy.push_back(make_pair(S.substr(i,mid),i));
            }
            sort(all(happy));
            for(int i=0;i<happy.size() && !can;i++){
                for(int j=i+1;j<happy.size() && !can;j++){
                    if(happy[i].first==happy[j].first){
                        if(happy[i].second+mid<=happy[j].second){
                            can=true;
                            break;
                        }
                    }
                    else{
                        break;
                    }
                }
            }
        }
        if(can)left=mid;
        else right=mid;
    }
    cout << left;

    


}

/*



 */


Measured memory_bytes: 6576
#include <cstdint>
#include <iostream>

using namespace std;

int32_t main()
{
  int32_t A, B, C, D, E, F;

  cin >> A >> B >> C >> D >> E >> F;

  int32_t water = 0;
  int32_t sugar = 0;

  for (int32_t i = 0; (100 * A * i) <= F; i++) {
    for (int32_t j = 0; (100 * A * i) + (100 * B * j) <= F; j++) {
      for (int32_t k = 0; (100 * A * i) + (100 * B * j) + (C * k) <= F; k++) {
        for (int32_t l = 0; (100 * A * i) + (100 * B * j) + (C * k) + (D * l) <= F; l++) {
          int32_t x = A * 100 * i + B * 100 * j;
          int32_t y = C * k + D * l;
          if (((y * 100) <= (x * E)) && ((sugar * (x + y)) <= (y * (water + sugar)))) {
            water = x;
            sugar = y;
          }
        }
      }
    }
  }

  cout << water + sugar << " " << sugar << endl;

  return 0;
}


Measured memory_bytes: 256
n=[]
while (a=gets)!=nil
    n<< a.split.map(&:to_i)
end
n.each{|e|
    exit if e[0]==e[1]&&e[0]==0
    now=0
    loop do
        case (now%2)
        when 0
            e[1].times{|i|print i.even?? "#":"."}
            puts;now+=1
        when 1
            e[1].times{|i|print i.even?? ".":"#"}
            puts;now+=1
        end
        if now==(e[0])
            puts;break    
        end
    end
}


Measured memory_bytes: 6884
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define endl "\n"
using namespace std;
const int MD=1e9+7;
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(NULL);
	ll n,k;
	cin>>n>>k;
	ll ch=n+1,ans=0;
	ll mn=0,mx=n,ale=0,ari=0;
	for(int i=1;i<n+1;i++){
		ale+=mn;
		ari+=mx;
		mn++;
		mx--;
//		ale%=MD;
//		ari%=MD;
		if(i<k)continue;
		else{
			ans+=ari-ale+1;
			ans%=MD;
		}
	}
	ans++;
	ans%=MD;
	cout<<ans;
}


Measured memory_bytes: 3632
// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
void solve();
int main() { solve(); return 0; }

vector<string> Z { "WA", "AC" };

#include <map>
void solve() {
  string s;
  cin >> s;
  int n=s.size();
  bool ans = s[0] == 'A' and islower(s[1]);
  int cnt = 0;
  loop(i,2,n-1) {
    ans = ans and (s[i] == 'C' or islower(s[i]));
    cnt += s[i] == 'C';
  }
  ans = ans and islower(s[n-1]);
  ans = ans and cnt == 1;
  cout << Z[ans] << endl;
}


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

#define ll long long
#define ar array

const int mxN=5e5, M=1e9+7;
int n, m;
ll iv[mxN+1], f1[mxN+1], f2[mxN+1];

ll nck(int n, int k) {
	return f1[n]*f2[k]%M*f2[n-k]%M;
}

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

	iv[1]=1;
	for(int i=2; i<=mxN; ++i)
		iv[i]=M-M/i*iv[M%i]%M;
	f1[0]=f2[0]=1;
	for(int i=1; i<=mxN; ++i) {
		f1[i]=f1[i-1]*i%M;
		f2[i]=f2[i-1]*iv[i]%M;
	}

	cin >> n >> m;
	ll ans=0;
	for(int i=0; i<=n; ++i) {
		ll c=i&1?M-1:1;
		c=c*nck(n, i)%M*nck(m, i)%M*f1[i]%M*nck(m-i, n-i)%M*nck(m-i, n-i)%M*f1[n-i]%M*f1[n-i]%M;
		ans=(ans+c)%M;
	}
	cout << ans;
}


Measured memory_bytes: 15380
fn main() {
    let stdin = std::io::stdin();
    let mut sc = Scanner::new(stdin.lock());
    loop {
        let n: usize = sc.read();
        let m: usize = sc.read();
        let p: Vec<usize> = sc.read_vec(n);
        if n == 0 {
            break;
        }
        let mut answer = 0;
        for (i, x) in p.iter().enumerate() {
            for (j, y) in p.iter().enumerate() {
                if i == j {
                    continue;
                }
                if x + y <= m && answer < x + y {
                    answer = x + y;
                }
            }
        }
        if answer != 0 {
            println!("{}", answer);
        } else {
            println!("NONE");
        }
    }
}

pub struct Scanner<R> {
    reader: R,
}

impl<R> Scanner<R> {
    pub fn new(reader: R) -> Scanner<R> {
        Scanner { reader }
    }
}

fn is_whitespace(b: u8) -> bool {
    b == b' ' || b == b'\n' || b == b'\r' || b == b'\t'
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        let buf = std::io::Read::bytes(self.reader.by_ref())
            .map(|b| b.expect("Read failed"))
            .skip_while(|&b| is_whitespace(b))
            .take_while(|&b| !is_whitespace(b))
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error")
    }

    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn read_chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}



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

using namespace std;
using ll = long long;

int main() {
    ll H;
    cin >> H;
    ll n = 1;
    while(true) {
        if(H != 1) {
            H /= 2;
            n ++;
        } else {
            break;
        }
    }
    cout << (ll)(pow((ll)2,(ll)n) - (ll)1) << endl;


    return 0;
}

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


def main():
    """Function."""
    a, b = map(int, input().split())
    if a % 3 == 0 or b % 3 == 0 or (a+b) % 3 == 0:
        print("Possible")
    else:
        print("Impossible")


if __name__ == "__main__":
    main()


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

using namespace std;
typedef long long ll;
typedef unsigned long ul;
typedef pair<ul, ul> P;
const int INF = 1e9;
const int MOD =1e9+7;
const ll LINF = 1e18;

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

    for(int i = 0; i < S.length(); i = i + 2) {
        if (S[i] == 'L') {
            cout << "No" << endl;
            return 0;
        }
    }

    for(int i = 1; i < S.length(); i = i + 2) {
        if (S[i] == 'R') {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
} 

Measured memory_bytes: 256
#include <iostream>

using namespace std;

 

int main()
{
   int i, a, b, c;
   
   for(i = 1; i <= 3000; i++)
   {
   cin >> a >> b;
   if(a==0 && b==0)
      break;
   
   if (a > b)
   
   {
  
   c=a;
   a=b;
   b=c;
       
   }
       
       cout << a << " " << b << endl;
   }
}


Measured memory_bytes: 3016
#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<iomanip>
#define BUG puts("no bug")
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define REP(a,b,c) for(ll a=b;a<=c;a++)
#define PER(a,b,c) for(ll a=b;a>=c;a--)
#define lb(a) (a&(-a))
#define pp (p<<1)
#define ppp (p<<1|1)
#define pi pair<ll,ll>
#define pii pair<pair<ll,ll>,ll>
using namespace std;
const double Pi=acos(-1.0);
const ll MAXN=1e6+5;
ll n,m,t;
ll v[MAXN];
char s[MAXN];
int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    a=abs(a);
    ll need=a/c;
    if(need>b){
        cout<<a-b*c;
    }
    else {
        ll ans=a-need*c;
        ll left=b-need;
        if(left%2){
            ans=c-ans;
        }
        cout<<ans;
    }
}

Measured memory_bytes: 3192
use proconio::input;

fn main() {
  input! {
    n: usize,
  }
  
  let max_value = 100_000;
  let mut dp: Vec<usize> = vec![max_value+1;max_value+1];
  let mut choices: Vec<usize> = vec![1];
  dp[1] = 1;
  
  let mut v = 6;
  while v <= max_value {
    dp[v] = 1;
    choices.push(v);
    v *= 6;
  }

  let mut v = 9;
  while v <= max_value {
    dp[v] = 1;
    choices.push(v);
    v *= 9;
  }
  
  for i in 2..=max_value {
    for v in choices.iter() {
      if &i < v { continue }
      let mut temp = std::cmp::min(dp[i-v]+1, dp[i-1]+1);
      dp[i] = std::cmp::min(dp[i], temp);
    }
  }
  
  println!("{}", dp[n]);
}

Measured memory_bytes: 2776
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n=0;
  string S,T;
  cin >> S >> T;
  for(int i=0;i<3;i++){
      if(S.at(i)==T.at(i)){
          n++;
      }
  }
  cout << n << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N;
int A[110];

signed main(){
	cin>>N;
	REP(i,N){
		cin>>A[i];
	}
	REP(i,N){
		if(A[i]%2==0){
			if(A[i]%3!=0&&A[i]%5!=0){
				cout<<"DENIED"<<endl;
				return 0;
			}
		}
	}
	cout<<"APPROVED"<<endl;
	return 0;
}


Measured memory_bytes: 256
h,w =map(int,input().split())
ls = []
for i in range(h):
    ls.append(list(input()))
ma = [[(10**9)]*w for i in range(h)]
if ls[0][0] == "." :
    ma[0][0] = 0
else:
    ma[0][0] =1
delta = [(-1,0),(0,-1)]
for y in range(h):
    for x in range(w):
        for dy,dx in delta:
            if 0<=y+dy<=h-1 and 0<=x+dx<=w-1 :
                if ls[y][x] == ls[y+dy][x+dx]:
                    ma[y][x] = min(ma[y+dy][x+dx],ma[y][x])
                else:
                    if ls[y][x] =="#":
                        cnt = 1
                    else:
                        cnt =0
                    ma[y][x] = min(ma[y][x],ma[y+dy][x+dx]+cnt)
print(ma[h-1][w-1])


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

const int N = 100005, ABC = 10004, INF = 1000000009;

int n, a, b, c, dp[N][3];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a >> b >> c;
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a;
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b;
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c;
    }
    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  bool ok=1;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    if(a%2==0){
      if(a%3!=0 && a%5!=0){
        ok=0;
      }
    }
  }
  if(ok)cout << "APPROVED\n";
  else cout << "DENIED\n";
}

Measured memory_bytes: 3604
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int GCD(const int& a, const int& b){
   const int& _a = max(a,b);
   const int& _b = min(a,b);
   if(_a % _b == 0){
      return _b;
   }
   else{
      return GCD(_b, _a % _b);
   }
}

int LCM(const int& a, const int& b){
   const int& _a = max(a,b);
   const int& _b = min(a,b);
   return (_a*_b)/(GCD(_a, _b));
}

int Factrial(const int& n){
   int ans = 1;
   for(int i = 1; i <= n; i++){
      ans *= i;
   }
   return ans;
}

int main(){
   int A, B, C;
   cin >> A >>B >> C;
   int cnt = 0;
   while(B - A >= 0){
      B -= A;
      cnt++;
      if(cnt == C){
         cout << C << endl;
         return 0;
      }
   }
   cout << cnt << endl;
   return 0;
}

Measured memory_bytes: 256
// see https://gist.github.com/LumaKernel/ff55d49ee1af69b7388f15b707e75c15
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>
#include <random>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<P> VP;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

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

#define LFOR(i,a,b) for(ll i=(a);i<(b);++i)
#define RLFOR(i,b,a) for(ll i=(b)-1;i>=(a);--i)

#define ALL(a) (a).begin(),(a).end()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define MP make_pair
#define PB push_back
#define EACH(i,c) REP(i,(int)(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define dump(x) cerr << "[L " << __LINE__ << "] " << #x << " = " << (x) << "\n";
#define dump2(x,y) cerr << "[L " << __LINE__ << "] " << #x << " = " << (x)\
			<< " , " << #y << " = " << (y) << "\n";

const int INF = 1e9;
const double EPS = 1e-10;

int n,m, a[4];
ll k;
string s;

int main() {
	cin >> n;
//	REP(i, n){
//		cin >> s;
//	}

//	int ans = 0;
//
//	cout << ans;

	REP(i, 4){
		a[i]=n%10;
		n/=10;
	}

	cout << (a[1]==a[2] && (a[0] ==a[1] || a[2] == a[3]) ? "Yes" : "No") << endl;
}


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

typedef unsigned long long ull;


int main(int argc, char const *argv[]) {
    int N, A;
    std::cin >> N >> A;

    std::vector<int> x(N);
    for (int i = 0; i < N; i++) {
        std::cin >> x[i];
    }

    std::vector<std::vector<std::vector<ull> > > dp(N+1);
    for (int i = 0; i < N+1; i++) {
        dp[i].resize(N+1);
        for (int j = 0; j <= N; j++) {
            dp[i][j].resize(N*A+1, 0);
        }
    }

    dp[0][0][0] = 1;
    for (int k = 1; k <= N*A; k++) {
        dp[0][0][k] = 0;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= N; j++) {
            for (int k = 0; k <= N*A; k++) {
                if (j > 0 && k >= x[i]) {
                    dp[i+1][j][k] = dp[i][j][k] + dp[i][j-1][k-x[i]];
                } else {
                    dp[i+1][j][k] = dp[i][j][k];
                }
            }
        }
    }

    ull ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += dp[N][i][i*A];
    }
    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 51200
#include <stdio.h>

int main(void)
{
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    while(1){
        c -= b;
        if(c<=0){
            printf("Yes");
            break;
        }
        a-=d;
        if(a<=0){
            printf("No");
            break;
        }
    }
}


Measured memory_bytes: 1700
#include <iostream>

int n, c[501],s[501],f[501];
//int anstime[101]={};

void solve(int a){
  if(a==n){
    std::cout<<0<<std::endl;
    return ;
  }else{
    int t=0;
    for(int i=a;i<=n-1;++i){
      if(t==0){
        t=c[i]+s[i];
      }else{
        if(t<s[i])t=s[i]+c[i];
        else{
          int t_=s[i];
          while(t>t_){
            t_+=f[i];
          }
          t=t_+c[i];
        }
      }
    }
    std::cout<<t<<std::endl;
  }
}

int main(){
  std::cin>>n;
  for(int i=1;i<n;++i){
    std::cin>>c[i]>>s[i]>>f[i];
  }
  for(int i=1;i<=n;++i){
    solve(i);
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int gcd (int a, int b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  if (a < b) swap(a, b);
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> x(++n);
  for (int i = 0; i < n; i++) cin >> x[i];
  sort(x.begin(), x.end());
  int g = x[1] - x[0];
  for (int i = 2; i < n; i++) {
    g = gcd(g, x[i] - x[i - 1]);
  }
  cout << g << '\n';
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

const int MOD = 1000000007;

int main(){
    int n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];

    sort(a.rbegin(), a.rend());
    int ans1 = a[0];

    int median1, median2;
    median1 = median2 = a[0]/2;
    if (a[0]% 2 == 0) median2 += 1;

    int min_diff = 1000000000;
    int ans2 = 0;
    for (int i = 1; i < n; i++){
        int diff = abs(a[0]-2*a[i]);
        if (min_diff > diff){
            min_diff = diff;
            ans2 = a[i];
        }
    }

    cout << ans1 << " " << ans2 << endl;
}

Measured memory_bytes: 4028
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
	int N,x = 0;
	scanf("%d",&N);
	for(int i = 1; i <= N; i++){
		x += i;
	}
	printf("%d",x);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;using ll=int_fast64_t;using ld=long double;using pll=pair<ll,ll>;using pld=pair<ld,ld>;
const ll INF=1LL<<60;void solve();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);solve();}
#define SELECTOR(_1,_2,_3,_4,SELECT,...) SELECT
#define rep(...) SELECTOR(__VA_ARGS__,_rep2,_rep1,_rep0)(__VA_ARGS__)
#define _rep0(i,n) for(ll i=0;i<n;++i)
#define _rep1(i,k,n) for(ll i=k;i<n;++i)
#define _rep2(i,k,n,d) for(ll i=k;d!=0&&d>0?i<n:i>n;i+=d)
template<class T> vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<class... Ts> auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
template<class T> inline bool chmax(T &a,const T &b){if(a<b){a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a,const T &b){if(a>b){a=b; return 1;} return 0;}
template<class T> void contout(const T &v){for(auto it=v.begin();it!=v.end();++it,cout<<(it!=v.end()?" ":"\n"))cout<<*it;}

const ll MOD=1e9+7;
void solve(){
  ll n; cin>>n;
  vector<vector<ll>> E(n);
  rep(_,n-1){
    ll x,y; cin>>x>>y;
    x--; y--;
    E[x].push_back(y);
    E[y].push_back(x);
  }
  auto dp=make_v(n,2,(ll)-1);
  function<void(ll,ll)> dfs=[&](ll v,ll p){
    if(dp[v][0]!=-1) return;
    ll white=1, black=1;
    for(ll &nv:E[v]){
      if(nv==p) continue;
      dfs(nv,v);
      white*=dp[nv][0]+dp[nv][1];
      white%=MOD;
      black*=dp[nv][0];
      black%=MOD;
    }
    dp[v][0]=white;
    dp[v][1]=black;
  };
  dfs(0,-1);
  cout<<(dp[0][0]+dp[0][1])%MOD<<"\n";
}

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

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 ll = long long;
using P = pair<ll,ll>;
using grid = vector<vector<int>>;

const int dx[2] = {1, 0};
const int dy[2] = {0, 1};
const int INF = 1<<30;
const ll mod = 998244353LL;

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

int main() {
    string S;
    cin>>S;
    if(S=="AAA"||S=="BBB") cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

Measured memory_bytes: 3536
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N), B(N);
  for(int i=0; i < N; i++){
      cin >> A[i] >> B[i];
  }
  
  //pair<int, int>はint２つの型
  vector<pair<int, int>> AB(N);
  for (int i=0; i < N; i++){
      AB[i] = make_pair(A[i], B[i]);
  }
  sort(AB.begin(), AB.end());
  
  long answer=0;
  for(int i=0; M > 0; i++){
      if(M>AB[i].second){
        answer += (long)AB[i].first* AB[i].second;
        M = M - AB[i].second;
    }
   else{
        answer += (long)AB[i].first * M;
        M = 0;
    }
  }
  cout << answer << endl;
  return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef std::vector<vector<int> > vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<vector<double>> vvd;
typedef vector<double> vd;

#define debugone(x) cerr << #x << " " << x << "\n"; cerr.flush();
#define debugtwo(x) cerr << #x << "-------------" << "\n";for(auto &it: x) cerr << it << " ";cerr << "\n"; cerr.flush();
#define debugthree(x_, i_, j_) cerr << #x_ << "------------" << "\n";cerr << "from " << i_ << " to " << j_ << "\n";for(ll k_=i_; k_<=j_; k_++) cerr << x_[k_] << " ";cerr << "\n"; cerr.flush();
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

const ll MOD = 1e9 + 7;
const int INF = 2e9;
const int MAX_LOG = 21;
const int MAX_N = 12800;

#define forn(i, n) for(int i = 0; i < n; i++)
#define forsn(i, s, n) for(int i = s; i < n; i++)
#define all(x) x.begin(), x.end()

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	map<pi, int> cnt;
	for(int i = 1; i <= n; i++){
		string s = to_string(i);
		int ld = s.back() - '0', fd = s.front() - '0';
		cnt[{fd, ld}]++;
	}
	ll total = 0;
	forsn(i, 1, n + 1){
		string s = to_string(i);
		int ld = s.back() - '0', fd = s.front() - '0';
		total += cnt[{ld, fd}];
	}
	cout << total << endl;
}		


Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = float('inf')


def LI(): return list(map(int, sys.stdin.readline().split()))


def I(): return int(sys.stdin.readline())


def LS(): return sys.stdin.readline().split()


def S(): return sys.stdin.readline().strip()


def IR(n): return [I() for i in range(n)]


def LIR(n): return [LI() for i in range(n)]


def SR(n): return [S() for i in range(n)]


def LSR(n): return [LS() for i in range(n)]


def SRL(n): return [list(S()) for i in range(n)]


def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

h,w,m= LI()
s=set()
D1=defaultdict(int)
D2=defaultdict(int)
for _ in range(m):
    h,w=LI()
    D1[h-1]+=1
    D2[w-1]+=1
    s.add((h-1,w-1))

A=[[v,i] for i,v in D1.items()]+[[-INF,-INF]]
B=[[v,i] for i,v in D2.items()]+[[-INF,-INF]]
A.sort(reverse=True)
B.sort(reverse=True)
a_now=0
b_now=0
ans=-INF
while True:
    av,ak=A[a_now]
    bv,bk = B[b_now]
    ans=max(ans,av+bv-int((ak,bk) in s))
    if a_now==len(A)-2 and b_now==len(B)-2:
        break
    elif A[a_now+1][0]+B[b_now][0]>A[a_now][0]+B[b_now+1][0]:
        a_now+=1
    else:
        b_now+=1

print(ans)






Measured memory_bytes: 209764
import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
a = na()
a.sort(reverse=True)
alice = sum(a[::2])
bob = sum(a[1::2])
print(alice - bob)

Measured memory_bytes: 3064