akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var n = cin.ReadInt;
            var inputArray = new int[n];
            for (int i = 0; i < n; i++)
            {
                inputArray[i] = cin.ReadInt;
            }

            if ( n == 1 ) {
                System.Console.WriteLine("Yes");
                return;
            }
            
            for (int i = n - 1; i > 0; i--)
            {
                if (inputArray[i] - inputArray[i-1] < 0)
                {
                    inputArray[i-1] -= 1;
                }
                if(inputArray[i] - inputArray[i-1] < 0)
                {
                    System.Console.WriteLine("No");
                    return;
                }
            }
            System.Console.WriteLine("Yes");
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}


Measured memory_bytes: 32988
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

void solve(){
     int n,k;cin >> n >> k;
     vector<int>a(n);
     for(int i = 0;i<n;i++) cin >> a[i];
     for(int i = k;i<n;i++){
        if(a[i-k]<a[i])cout <<"Yes"<<endl;
        else cout <<"No"<<endl;
     }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 3940
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

const double EPS = 1e-9;

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

	for ( int n; cin >> n, n; )
	{
		VI is( n );
		FOR( i, is )
		{
			cin >> i;
		}

		double minh = DBL_MAX;
		int res_s, res_a, res_c;
		REP( s, 0, 16 )
		{
			REP( a, 0, 16 )
			{
				REP( c, 0, 16 )
				{
					VI rs( n + 1 );
					rs[0] = s;
					REP( i, 0, n )
					{
						rs[ i + 1 ] = ( a * rs[i] + c ) % 256;
					}

					VI os( n );
					REP( i, 0, n )
					{
						os[i] = ( is[i] + rs[ i + 1 ] ) % 256;
					}

					double tmp = 0;
					REP( x, 0, 256 )
					{
						double cnt = count( ALL( os ), x );
						if ( cnt == 0 )
						{
							continue;
						}
						tmp -= ( cnt / n ) * log( cnt / n );
					}
					if ( tmp + EPS < minh )
					{
						minh = tmp;
						res_s = s;
						res_a = a;
						res_c = c;
					}
				}
			}
		}

		cout << res_s << ' ' << res_a << ' ' << res_c << endl;
	}

	return 0;
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
using namespace std;
long long digit_sum(long long n, long long base) {
  assert(base >= 2);
  long long res = 0;
  while (n) {
    res += n % base;
    n /= base;
  }
  return res;
}
signed main() {
  cin.tie(0); ios::sync_with_stdio(false);
  long long n, s; cin >> n >> s;
  for (long long b = 2; b * b <= n; b++) {
    if (digit_sum(n, b) == s) {
      cout << b << '\n';
      return 0;
    }
  }
  for (long long a1 = sqrt(n) + 1; a1 >= 1; a1--) {
    if ((n - s) % a1 == 0) {
      long long b = (n - s) / a1 + 1;
      if (sqrt(n) < b and b <= n and a1 < b and 0 <= s - a1 and s - a1 < b) {
        cout << (n - s) / a1 + 1 << '\n';
        return 0;
      }
    }
  }
  cout << (s == n ? n + 1 : -1) << '\n';
  return 0;
}

Measured memory_bytes: 256
class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1
      
N,M=map(int,input().split())
B=[]
for i in range(M):
  a,b=map(int,input().split())
  B.append((a,b))

def solve(x):
  a,b=B[x]
  uf=UnionFind(N+1)
  for i in range(M):
    if i!=x:
      uf.union(B[i][0],B[i][1])
  if uf.find(a)==uf.find(b):
    return False
  else:
    return True

ans=0
for i in range(M):
  if solve(i):
    ans+=1
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long; 
int main(){
  ll N;
  cin>>N;
  vector<ll>tr(N);
  if(N==1||N==2){
    cout<<0<<endl;
    
  }
  else{
  for(ll i=0;i<N;i++){
    cin>>tr.at(i);
  }
  ll n=0;
  
  sort(tr.begin(),tr.end());
  for(ll i=0;i<N-2;i++){
    for(ll j=i+1;j<N-1;j++){
      if(tr.at(i)!=tr.at(j)){
        
      
      for(ll k=j+1;k<N;k++){
        if(tr.at(k)!=tr.at(j)){
        if(tr.at(i)+tr.at(j)>tr.at(k)){
            n+=1;
          
          
        }
        }
          }
        }
      }
  }
  cout<<n<<endl;
  }


  
}

Measured memory_bytes: 3620
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 998244353;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;

ll modadd(ll x, ll y) {
    return ((x + y) % mod + mod) % mod;
}

ll multiply(ll x, ll y) {
    return (x % mod) * (y % mod) % mod;
}

ll po[210];

int main() {
    ll N;
    cin >> N;
    plglg pt[N];
    REP(i, 0, N) {
        ll x, y;
        cin >> x >> y;
        pt[i] = plglg(x, y);
    }
    sort(pt, pt + N);
    po[0] = 1;
    REP(i, 1, 210) {
        po[i] = multiply(po[i - 1], 2);
    }
    xy_t pt2[N];
    REP(i, 0, N) {
        pt2[i] = xy_t(pt[i].first, pt[i].second);
    }
    ll difnum = 0;
    REP(k, 0, N) {
        vector<pdlg> vec;
        xy_t base = pt2[k];
        REP(i, k + 1, N) {
            xy_t tar = pt2[i];
            double ab = abs(tar - base);
            xy_t dif = (tar - base) / ab;
            double d = dif.imag();
            bool ok = false;
            REP(j, 0, vec.size()) {
                pdlg p = vec[j];
                if (abs(d - p.first) < eps) {
                    vec[j].second++;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                vec.push_back(pdlg(d, 1));
            }
        }
        REP(i, 0, vec.size()) {
            ll p = vec[i].second;
            if (p > 1) {
                ll zero = 1;
                ll one = p;
                ll sum = zero + one;
                difnum = modadd(difnum, modadd(po[p], - sum));
            }
        }
    }
    ll anssum = 1 + N + N * (N - 1) / 2;
    //cout << anssum << " " << difnum << endl;
    ll ans = modadd(po[N], - modadd(anssum, difnum));
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,ans,k;
int main()
{
    cin>>a>>b>>c>>d>>e;
    k=min(a*4,min(b*2,c));
    if(k*2<=d)
        cout<<k*e<<endl;
    else
        cout<<(e%2)*k+e/2*d<<endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

N = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(N[int(input())-1])


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

// global variables
#define debug(x) cout << #x << ": " << x << endl
typedef long long ll;
const int M = 1e9 + 7;
const int INF = 1e9;

// typedef
typedef pair<int, int> P;
// sort by P.first (asd)
bool comPair(const P &firstElof, const P &secondElof) {
    return firstElof.first < secondElof.first;
}

// moving 4-direction
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

#define MAX_N 100000 //10^5

int par[MAX_N];       // 親
int rank_tree[MAX_N]; // 木の深さ

// n要素で初期化
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rank_tree[i] = 0;
    }
}

// 木の根を求める
int root(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = root(par[x]);
    }
}

// xとyの属する集合を併合
void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return;

    if (rank_tree[x] < rank_tree[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rank_tree[x] == rank_tree[y]) rank_tree[x]++;
    }
}

// xとyが同じ集合に属するか否か
bool same(int x, int y) {
    return root(x) == root(y);
}

int main() {
    int n, m;
    int s, t, k;
    vector<int> p;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> k;
        k--;
        p.push_back(k);
    }
    init(n);
    for (int i = 0; i < m; i++) {
        cin >> s >> t;
        s--;
        t--;
        unite(s, t);
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (root(p[i]) == root(i) || p[i] == i) cnt++;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 1528
//Exp val.
//https://atcoder.jp/contests/dp/tasks/dp_j
//https://codeforces.com/blog/entry/64250?#comment-523543
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD (1000000007)
//#define MOD (998244353)
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
//ifstream cinn("input.txt");ofstream coutt("output.txt");

int n;
int dp[400][400];
int v[400];

int sum(int i,int j){
    if(i==0)return v[j];
    return v[j]-v[i-1];
}

int f(int i,int j){
    if(i==j)return 0;
    
    int &ans=dp[i][j];
    if(ans!=-1)return ans;
    ans=INF;
    for(int k=i;k<j;k++){
        ans=min(ans,f(i,k)+f(k+1,j)+sum(i,j));
    }
    return ans;
}

signed main(){
    FASTER;
    memset(dp,-1,sizeof dp);
    cin>>n;
    for(int i=0;i<n;i++)cin>>v[i];
    for(int i=1;i<n;i++)v[i]+=v[i-1];
    cout<<f(0,n-1);
}


Measured memory_bytes: 1536
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;
#define LL long long

LL N,ans=0;
pair<LL,LL>bot[100001];

int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		int X,L;
		cin>>X>>L;
		bot[i]={X+L,X-L};
	}
	sort(bot,bot+N);
	LL r = -10000000000;
	for(int i=0;i<N;i++){
		if(r<=bot[i].second){
			ans++;
			r=bot[i].first;
		}
	}
	cout<<ans<<endl;
	return 0;
}


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


void print_sharp(){
    cout<<"####################"<<endl;
}

void print(ll building[3][10]){
    rep(i,3){
        rep(j,10) cout<<" "<<building[i][j];
        cout<<endl;
    }
}

int main(){
    cout<<fixed<<setprecision(10);

    ll m,f,r;
    cin>>m>>f>>r;
    
    while(m!=-1 || f!=-1 || r!=-1){
        if(m==-1 || f==-1) cout<<'F'<<endl;
        else if(m+f >= 80) cout<<'A'<<endl;
        else if(m+f >= 65 ) cout<<'B'<<endl;
        else if(m+f >= 50) cout<<'C'<<endl;
        else if(m+f >= 30){
            if(r >= 50) cout<<'C'<<endl;
            else cout<<'D'<<endl;
        }else{
            cout<<'F'<<endl;
        }
        
        cin>>m>>f>>r;
    }

    

    return 0;
}








Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int N,K;
    cin >> N >> K;
    vector<int> vec(N);
    rep(i,N){
        cin >> vec[i];
    }
    if (K <= 100){
        for (int i = 1; i <= K; i++){
            vector<int> vec_copy(N + 1,0);
            rep(j,N){
                if (j - vec[j] < 0){
                    vec_copy[0]++;
                }
                else{
                    vec_copy[j - vec[j]]++;
                }
                if (j + 1 + vec[j] >= N){
                    vec_copy[N]--;
                }
                else{
                    vec_copy[j + 1 + vec[j]]--;
                }
            }
            rep(j,N){
                vec_copy[j + 1] += vec_copy[j];
            }
            rep(j,N){
                vec[j] = vec_copy[j];
            }
        }
    }
    else{
        for (int i = 1; i <= 100; i++){
            vector<int> vec_copy(N + 1,0);
            rep(j,N){
                if (j - vec[j] < 0){
                    vec_copy[0]++;
                }
                else{
                    vec_copy[j - vec[j]]++;
                }
                if (j + 1 + vec[j] >= N){
                    vec_copy[N]--;
                }
                else{
                    vec_copy[j + 1 + vec[j]]--;
                }
            }
            rep(j,N){
                vec_copy[j + 1] += vec_copy[j];
            }
            rep(j,N){
                vec[j] = vec_copy[j];
            }
        }
    }
    rep(i,N - 1){
        cout << vec[i] << " ";
    }
    cout << vec[N - 1] << endl;
}


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

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

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

  vector <int> b(B);
  for(int j = 0; j < B; j++){
    cin >> b.at(j);
  }

  vector <int> x(M) , y(M) , c(M);
  for(int i = 0; i < M; i++){
    cin >> x.at(i) >> y.at(i) >> c.at(i);
    --x.at(i); --y.at(i);
  }
  int answer = a.at(x.at(0)) + b.at(y.at(0)) - c.at(0);
  for(int i = 0; i < M; i++){
    if(answer > a.at(x.at(i)) + b.at(y.at(i)) - c.at(i)){
      answer = a.at(x.at(i)) + b.at(y.at(i)) - c.at(i);
    }
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  if(answer < a.at(0) + b.at(0)){
    cout << answer << endl;
  }
  else{
    cout << a.at(0) + b.at(0) << endl;
  }
}


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

void solve(int N){
    int ans;
    ans = 0;
    string s_i, dup;
    vector<string> s;
    for (int i=0; i<N; i++){
        cin >> s_i;
        for (auto x : s){
            if(x==s_i){
                dup = x;
                break;
            }
        }
        if(dup==s_i){
            continue;
        }
        s.push_back(s_i);
        ans++;
    }
    cout << ans << endl;
    return;
}

void solve_set(int N){
    set<string> S;
    for(int i=0; i<N; i++) {
        string s_i;
        cin >> s_i;
        S.insert(s_i);
    }
    cout << S.size() << endl;
    return;
}

int main(){
    int N;
    cin >> N;
    solve_set(N);
    return 0;
}


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

ll const MOD = 1e9 + 7;
int main() {
  ll n;
  cin >> n;
  vector<ll> t(n), a(n), poss(n);
  for(int i=0;i<n;i++) cin >> t[i];
  for(int i=0;i<n;i++) cin >> a[i];
  ll ans = 1;
  if(t[n-1] != a[0]) {
    ans = 0;
  }
  poss[0] = poss[n-1] = 1;
  for(int i=1;i<n-1;i++) {
    if(t[i] > t[i-1])
      poss[i] = 1;
    else
      poss[i] = t[i];
  }
  for(int i=n-2;i>=0;i--) {
    if(a[i] > a[i+1]) {
      if(poss[i] == 1 && t[i] != a[i])
        ans = 0;
      if(poss[i] != 1 && t[i] < a[i])
        ans = 0;
      poss[i] = 1;
    } else {
      poss[i] = min<ll>(poss[i], a[i]);
    }
  }

  for(int i=0;i<n;i++) {
    ans *= poss[i];
    ans %= MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
const int mx=1e5+5;
bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
} 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int n;
	cin >> n;
	vector < pair <int,int> > a;
	rep(i,n){int x;cin >> x;a.push_back(make_pair(x,i+1));}
	sort(a.begin(),a.end());
	rep(i,n){
		cout << a[i].nd << " ";
	}

	cout << endl;
}


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

typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<ll> a(N), s(N + 1, 0);
    rep(i, N) {
        cin >> a[i];
        s[i + 1] = s[i] + a[i];
    }
    ll ans = 1e18;
    rep(i, N - 1) {
        ll b = abs(s[N] - s[i + 1] - s[i + 1]);
        if (b < ans) ans = b;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("03")
#pragma GCC optimization ("unroll-loops")
using namespace std;

const int maxn = 100002;
const int maxe = 20;
int n,m,c=0,k=0,d=0,pa[maxn];
string s;
int a[maxn];
int st[maxn][maxe];

void build(int n){
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }
}

int query(int a, int b){
    int k = 31- __builtin_clz(b-a+1);
    return min(st[a][k], st[b-(1<<k)+1][k]);
}

int find(int i)
{
    if(pa[i]==i)return i;
    return pa[i]=find(pa[i]);
}

int bs(int l,int r,int x)
{
    while(l!=r)
    {
        int mi=(l+r)/2;
        if(a[mi]>x)r=mi;
        else l=mi+1;
    }
}

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

    cin>>n;
    for(int i=1;i<=n;i++){
    cin>>a[i];
    }
    for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    if(i==j)continue;
    c+=a[i]*a[j];
    }
    }
    cout<<c/2;
}


Measured memory_bytes: 2304
import scala.collection.mutable
import scala.io.Source.stdin

/**
  * AOJ
  */
object Main {

  val alphabet = "abcdefghijklmnopqrstuvwxyz"

  def main(args: Array[String]): Unit = {

    val alphabetMap = mutable.Map.empty[Char, Int]
    setValues(alphabetMap)
    for(c <- alphabet){
      println(c + " : " + alphabetMap(c).toString)
    }
  }

  def setValues(alphabetMap:mutable.Map[Char,Int]):Unit = {
    for (c <- alphabet) {
      alphabetMap += c -> 0
    }
    for (line <- stdin.getLines()){
      if (line.length == 0) {
        return
      }
      for(c <- line.toLowerCase) {
        if (alphabetMap.contains(c)) {
          alphabetMap(c) += 1
        }
      }
    }
  }
}

Measured memory_bytes: 44148
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
set<int>s;
struct Node{
	int x,y,col;
	bool operator < (const Node &b) const {
		return x < b.x;
	}
}a[maxn<<1];

inline int read(void)
{
	int x = 0,f = 1; char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x * f;
}
int main(int argc, char *argv[])
{
	int N = read(),ans = 0;
	for (int i = 1; i <= N; i++) a[i].x = read(),a[i].y = read(),a[i].col = 1;
	for (int i = N+1; i <= (N<<1); i++) a[i].x = read(),a[i].y = read(),a[i].col = 2;
	sort(a+1,a+(N<<1)+1);
	for (int i = (N<<1); i >= 1; i--)
	{
		if (a[i].col == 2) s.insert(a[i].y);
		else 
		{
			set<int>::iterator it = s.lower_bound(a[i].y);
			if (it != s.end())
			{
				s.erase(it);
				ans ++;
			}
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, p, q, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    p -= 1
    q -= 1

    if len(G[p]) == 1 and G[p][0] == q:
        print(0)
        return

    dist1 = [-1] * N
    dist1[p] = 0
    queue1 = deque([p])
    while queue1:
        v = queue1.popleft()
        for nv in G[v]:
            if dist1[nv] == -1:
                dist1[nv] = dist1[v] + 1
                queue1.append(nv)

    dist2 = [-1] * N
    dist2[q] = 0
    queue2 = deque([q])
    while queue2:
        v = queue2.popleft()
        for nv in G[v]:
            if dist2[nv] == -1:
                dist2[nv] = dist2[v] + 1
                queue2.append(nv)

    max_dist = -1
    for d1, d2 in zip(dist1, dist2):
        if d1 < d2 and max_dist < d2:
            max_dist = d2

    print(max_dist - 1)
    return


if __name__ == '__main__':
    main()


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

int main(){
    int s;
    cin>>s;
    if(s/100>=1 && s/100<=12){
        if(s%100>=1 && s%100<=12){
            cout<<"AMBIGUOUS"<<endl;
        }else{
            cout<<"MMYY"<<endl;
        }
    }else{
        if(s%100>=1 && s%100<=12){
            cout<<"YYMM"<<endl;
        }else{
            cout<<"NA"<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
using llong = long long;

llong n;
llong a[200005];
llong b[200005];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];

    sort(a, a + n);
    sort(b, b + n);

    if (n & 1) {
        cout << b[n / 2] - a[n / 2] + 1 << endl;
    }
    else {
        llong ans = 0;
        llong s, t;

        s = (a[n / 2] + a[n / 2 - 1] + 1) / 2;
        t = (b[n / 2] + b[n / 2 - 1]) / 2;

        ans += t - s + 1 + t - s;
        if ((a[n / 2] + a[n / 2 - 1]) % 2) ans++;
        if ((b[n / 2] + b[n / 2 - 1]) % 2) ans++;

        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 6724
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int ans = 700;
        for(int i = 0; i < 3; i++){
            if(s.charAt(i) == 'o') ans += 100;
        }
        System.out.println(ans);
    }
}

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


int main(){
    int x, y, z;
    cin >> x >> y >> z;
    x -= z;
    int ans = 0;
    while(x-y-z >= 0){
        x -= y+z;
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
MOD=10**9+7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
N=int(input())
A=list(map(int,input().split()))
ans=ModInt(0)
Divisor=dict([(i,0) for i in range(1000000)])
def frac(n,div):
    ret = 0
    while not (n % div) :
        n //= div
        ret += 1
    return ret,n
for i in A:
    divided=i
    for j in range(2,int(divided**(0.5)+2)):
        chk,divided = frac(divided,j)
        if chk > Divisor[j]:Divisor[j] = chk
    Divisor[divided] = max(1,Divisor[divided])
LCM=ModInt(1)
for i in range(2,1000000):
    LCM*=i**ModInt(Divisor[i])
for i in A:
    ans+=LCM/ModInt(i)
print(ans)

Measured memory_bytes: 162912
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,a) for(ll i=0;i<a;i++)
#define jkl ll debug = 0;
#define RREP(i,a) for(ll i=a;i>0;i--)
#define rrep(i,a,b) for(ll i=a-1;i>=b;i--)
#define printall(n,array) {for(ll i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
#define mp make_pair
typedef long long ll;
typedef pair<ll, ll> Pi;
typedef pair<ll, Pi> V;
typedef vector<ll> VE;
const ll mod = 1e9 + 7; //10^9+7

int main() {
    ll A, B, Q;
    cin >> A >> B >> Q;
    VE a(A), t(B), x(Q);
    REP(i, A)cin >> a[i];
    REP(i, B)cin >> t[i];
    REP(i, Q)cin >> x[i];
    a.push_back(-1 * 1e18);
    t.push_back(-1 * 1e18);
    a.push_back(1e18);
    t.push_back(1e18);
    sort(a.begin(), a.end());
    sort(t.begin(), t.end());
    ll Na[2];
    ll Nt[2];
    REP(i, Q){
        ll res = 1e18;
        Na[0] = lower_bound(a.begin(), a.end(), x[i]) - a.begin();
        Na[1] = Na[0] - 1;
        Nt[0] = lower_bound(t.begin(), t.end(), x[i]) - t.begin();
        Nt[1] = Nt[0] - 1;
        REP(n, 2)REP(m, 2){
            ll dist1 = abs(x[i] - a[Na[n]]) + abs(a[Na[n]] - t[Nt[m]]);
            ll dist2 = abs(x[i] - t[Nt[m]]) + abs(t[Nt[m]] - a[Na[n]]);
            res = min({res, dist1, dist2});
        }
        print(res);
    }

}


Measured memory_bytes: 3680
function Main(input) {
  var tmp = input.trim().split("\n");
  var XYZK = tmp[0].split(/\s/).map(val => Number(val));
  var X = XYZK[0];
  var Y = XYZK[1];
  var Z = XYZK[2];
  var K = XYZK[3];
  var AAry = tmp[1].split(/\s/).map(val => Number(val));
  var BAry = tmp[2].split(/\s/).map(val => Number(val));
  var CAry = tmp[3].split(/\s/).map(val => Number(val));
 
  AAry.sort((a, b) => b - a);
  BAry.sort((a, b) => b - a);
  CAry.sort((a, b) => b - a);
 
  var ABSumAry = [];
  var ABCSumAry = [];
 
  for (var i = 0; i < X; i++) {
    for (var j = 0; j < Y; j++) {
      ABSumAry.push(AAry[i] + BAry[j]);
    }
  }
 
  ABSumAry.sort((a, b) => b - a);
 
  for (var k = 0; k < Math.min(K, ABSumAry.length); k++) {
    for (var l = 0; l < Math.min(Z,K); l++) {
      if (Math.min(K, ABSumAry.length) < k * l) break;
      ABCSumAry.push(ABSumAry[k] + CAry[l]);
    }
  }
  ABCSumAry.sort((a, b) => b - a);
 
  for (var m = 0; m < K; m++) {
    console.log(ABCSumAry[m]);
  }
}
 
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 94260
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

const ll mod=1e9+7;

//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

typedef pair<ll,ll> P;

ll calc(ll n){//1→xまでの排他的論理和の計算
  if(n%4==1){
    return 1;
  }else if(n%4==2){
    return 1^n;
  }else if(n%4==3){
    return 0;
  }else{
    return 0^n;
  }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    cin>>a>>b;
    if(a==0){
      cout<<calc(b)<<endl;
      return 0;
    }
    ll ans=calc(b)^calc(a-1);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.stdio;
import std.conv;
import std.string;
import std.range;

void main(){
    size_t w, h, sx, sy;
    char[][] data = new char[][](20, 20);
    while(true){
        auto input = readln.split;
        w = input[0].to!int;
        h = input[1].to!int;
        if(!(w | h)){
            break;
        }
        foreach(i; 0..h){
            foreach(j, c; readln.chomp){
                data[i][j] = c;
                if(c == '@'){
                    sx = j;
                    sy = i;
                    data[i][j] = '#';
                }
            }
        }
        data.dfs(sx, sy, w, h).writeln;
    }
}

enum move = [[1, 0], [0, 1], [-1, 0], [0, -1]];

size_t dfs(char[][] data, size_t sx, size_t sy, size_t w, size_t h){
    size_t count = 1;
    foreach(i; 0..4){
        size_t x = sx + move[i][0];
        size_t y = sy + move[i][1];
        if(0 <= x && x < w && 0 <= y && y < h && data[y][x] != '#'){
            data[y][x] = '#';
            count += dfs(data, x, y, w, h);
        }
    }
    return count;
}

Measured memory_bytes: 2068
def main():
    n, *a = map(int, open(0).read().split())
    ans = 1
    if a.count(0):
        print(0)
        exit()
    for i in a:
        ans *= i
        if ans > 10 ** 18:
            print(-1)
            break
    else:
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 21780
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
int f = 0;
int vis[100005];
vector<int>adj[100005];
void dfs(int ele)
{
    vis[ele] = 1;
    for(int i=0;i<adj[ele].size();i++)
    {
        if(!vis[adj[ele][i]])
        {
            vis[adj[ele][i]] = 1;
            dfs(adj[ele][i]);
        }
        else{
            if(adj[ele][i]!=ele)
            {
              //  f=1;
            }
        }

    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;

        adj[x].pb(y);
        adj[y].pb(x);
    }
    int cc=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            f = 0;
            dfs(i);
            if(f==0)
            {
                cc++;
            }
        }
    }
    cout<<cc<<endl;
}


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

const int maxn = 2e5 + 10;

int n;
long long s[maxn];
int lo[maxn], hi[maxn];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		s[i] += s[i - 1];
	}
	for (int i = 2, j = 1; i <= n; ++i) {
		while (abs(s[i] - 2 * s[j]) >= abs(s[i] - 2 * s[j + 1]) && j < i - 1) j++;
		lo[i] = j;
	}
	for (int i = n - 2, j = n - 1; i > 0; --i) {
		while (abs((s[n] - s[i]) - 2 * (s[n] - s[j])) >= abs((s[n] - s[i]) - 2 * (s[n] - s[j - 1])) && j > i + 1) j--;
		hi[i] = j;
	}
	long long answer = 1e18;
	//cout << s[lo[2]] << " " << s[hi[2]] << " " << s[2] - s[lo[2]] << " " << s[n] - s[hi[2]] << "\n";
	for (int i = 2; i <= n - 2; ++i) {
		long long x = max({s[lo[i]], s[hi[i]] - s[i], s[i] - s[lo[i]], s[n] - s[hi[i]]});
		long long y = min({s[lo[i]], s[hi[i]] - s[i], s[i] - s[lo[i]], s[n] - s[hi[i]]});
		answer = min(answer, x - y);
		//cout << i << " " << x << " " << y << "\n";
	}
	cout << answer << "\n";
	return 0;
}

Measured memory_bytes: 3328
#include <stdio.h>
int main(){
	int x[]={1,2,3,4,5,6,7,8,9,10};
	int a,b,c,sum=0,i;
	while(scanf("%d%d%d",&a,&b,&c)!=-1){
		for(i=0;i<10;i++){
			if(x[i]!=a){
			if(x[i]!=b){
			if(x[i]!=c){
			if(a+b+x[i]<=20) sum++;
			}}}}
		if(sum>=4){printf("YES\n");}
		else{printf("NO\n");}
		sum=0;
	}
		return 0;
}

Measured memory_bytes: 580
"""
奇数本で構成される閉路が存在している場合、全ての頂点同士を結ぶことができる
そうでない場合、、、
奇数本でつながっている辺同士は直接結ぶことができる＝グラフっは二部グラフとなっていて、
AグループとBグループのノード同士を結ぶことができる。
"""

import sys
sys.setrecursionlimit(200000)

N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]

for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

steps = [None]*(N+1)

def dfs(node,step):
    if steps[node] != None:
        if (step - steps[node])%2 == 1:
            return True
        else:
            return False
    else:
        steps[node] = step
        res = False
        for nx in edges[node]:
            res = res or dfs(nx,step+1)
        return res

res = dfs(1,0)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if res:
    print(choose(N,2)-M)
else:
    for i in range(1,N+1):
        steps[i] %= 2
    odd = steps.count(1)
    even = N - odd
    print(odd*even-M)



Measured memory_bytes: 37212
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import median

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()
ab = LI(n)

a = mycol(ab,0)
ma = median(a)

b = mycol(ab,1)
mb = median(b)

if n%2==1:
    ans = mb - ma + 1
else:
    ans = (mb-ma)*2 + 1
print(int(ans))

Measured memory_bytes: 136864
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<set>
#include<cstdlib>
#include<cctype>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 1e5 + 5;
const ll maxm = 1e3 + 5;
template<class T>
inline T qread(T &IEE){
	register T x = 0, f = 1;
	register char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-'){
			f = -f;
		}
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return IEE = x * f;
}
template<class T>
inline void qwrite(T a){
	if(!a){
		putchar('0');
		return ;
	}
 	if(a < 0){
		putchar('-');
		a = -a;
	}
	if(a > 9) qwrite(a / 10);
	putchar(a % 10 + 48);
	return ;
}
template<class T>
inline T ab(T a){
	return (a > 0) ? a : -a;
}
template<class T>
inline void swa(T &a, T &b){
	a ^= b ^= a ^= b;
	return ;
}
ll a, n;
set<ll> s;
int main(){
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	qread(n);
	for(int i = 1;i <= n;i++){
		qread(a);
		if(s.count(a)){
			s.erase(a);
		} else {
			s.insert(a);
		}
	}
	cout << s.size() << endl;
	return 0;
}


Measured memory_bytes: 4864
import java.util.Scanner;

public class Main {
	void run(){
		Scanner sc = new Scanner(System.in);
		char map[][] = new char[10][];
		String str = ".,!? ";
		map[1] = str.toCharArray();
		str = "abc";
		map[2] = str.toCharArray();
		str = "def";
		map[3] = str.toCharArray();
		str = "ghi";
		map[4] = str.toCharArray();
		str = "jkl";
		map[5] = str.toCharArray();
		str = "mno";
		map[6] = str.toCharArray();
		str = "pqrs";
		map[7] = str.toCharArray();
		str = "tuv";
		map[8] = str.toCharArray();
		str = "wxyz";
		map[9] = str.toCharArray();
		int n = sc.nextInt();
		while(n-- != 0){
			char ch[] = sc.next().toCharArray();
			int count = 0;
			int botan = 0;
			str = "";
			for(int i=0; i < ch.length; i++){
				if(ch[i] == '0'){
					if(count > 0){
						str += String.valueOf(map[botan][(count-1)%map[botan].length]);
						count = 0;
					}
					else{
						continue;
					}
				}
				else{
					count++;
					botan = ch[i]-'0';
				}
			}
			System.out.println(str);
		}
	}
	public static void main(String[] args) {
		//new AOJ2006().run();
		new Main().run();
	}

}

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

#define int long long
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
constexpr int MOD = 1e9 + 7;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vec>;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

template <typename T>
void init(vector<T>& v) {
    rep (i, v.size())
        cin >> v[i];
}

template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) {
    assert(v.size() == w.size());
    rep (i, v.size())
        cin >> v[i] >> w[i];
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vec a(n);
    init(a);
    vec b(m), c(m);
    init(b, c);

    vector<P> v;
    rep (i, n)
        v.pb({a[i], 1});
    rep (i, m)
        v.pb({c[i], b[i]});

    sort(all(v), greater<P>());

    int rest = n;
    int x = 0;
    repall (p, v) {
        if (p.second <= rest) {
            x += p.first * p.second;
            rest -= p.second;
        } else {
            x += p.first * rest;
            rest -= rest;
        }
        if (not rest) break;
    }
    print(x);

    return 0;
}


Measured memory_bytes: 8560
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

ll n;
ll a, b, c;
ll amax, bmax, cmax;
ll prova, provb, provc;

int main()
{
    cin >> n >> amax >> bmax >> cmax;
    for(int i = 2; i <= n; i++) {
        cin >> a >> b >> c;
        prova = a + max(bmax, cmax);
        provb = b + max(amax, cmax);
        provc = c + max(bmax, amax);
        amax = prova; bmax = provb; cmax = provc;
    }
    cout << max(amax, max(bmax, cmax));
    return 0;
}


Measured memory_bytes: 3576
n, s = int(input()), input()
dp = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            dp[i + 1][j + 1] = min(dp[i][j] + 1, j - i)
from itertools import chain
# max(i for i in chain.from_iterable(dp))
print(max(chain.from_iterable(dp)))


Measured memory_bytes: 264852
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: i64,
        b: i64,
        x: i64,
    }
    if a % x == 0 {
        println!("{}",(b - a) / x + 1);
    } else {
        println!("{}",(b - (a - a % x)) / x);
    }
}

Measured memory_bytes: 4352