akhauriyash/Code-Regression huggingface dataset:
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//main code

int main(int argc, char const* argv[])
{
    int n;
    cin >> n;
    vector<bool> swaped(n+1,false);
    VI p(n+1,0);
    p[0] = -1;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        if (p[i] == i) {
            if (p[i-1] == i-1 and !swaped[i-1]) {
                swaped[i] = true;
            }
            else {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define     ll          long long
#define     MOD         10e9+7
#define     pb          push_back
#define     vll         vector<long long>
#define     vi          vector<int>
#define     vl          vector<long>
#define     pii         pair<int, int>
#define     all(a)      (a).begin(),(a).end()
#define     rep(i,a,b)  for(int i=a;i<b;i++)
#define     MAX         100002 
#define     ios	      ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int main(){
      
      ios
      int a,b,c,d;
      cin >> a >> b >> c >> d;
      int i=1;
      while(i){
            
            if(i%2!=0){
                  c = c-b;
                  if(c<=0){
                        cout << "Yes" <<"\n";
                        break;
                  }      
            }
            else{
                  a=a-d;
                  if(a<=0){
                        cout << "No" <<"\n";
                        break;
                  }      
            }
            i++;
      }

      return 0;
}


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

using namespace std;

typedef long long ll;

double pi = 3.1416;

int main() {
  ll m; cin >> m;
  int n; cin >> n;
  ll sum = 0;
  for(int i = 0; i < n; i++) {
    ll x; cin >> x;
    sum += x;
  }
  if(sum > m) {
    printf("-1");
  }
  else {
    cout << m - sum << '\n';
  }
}

Measured memory_bytes: 3684
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] move_1 = new int[N];
		int[] move_N = new int[N];
		for(int i=0;i<N;i++){
			move_1[i] = 0;
			move_N[i] = 0;
		}
		for(int i=0;i<M;i++){
			int a = sc.nextInt();
			int b = sc.nextInt();
			if(a == 1)
				move_1[b-1] = 1;
			if(b == N)
				move_N[a-1] = 1;
		}
		for(int i=0;i<N;i++){
			if(move_1[i] == 1 && move_N[i] == 1){
				System.out.println("POSSIBLE");
				return;
			}
		}
		System.out.println("IMPOSSIBLE");
	}

}


Measured memory_bytes: 96816
#include <bits/stdc++.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
template <class T> using V = vector<T>;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(ll)(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
ll combi(ll n,ll m) {
  ll ans=1;
  rFOR(i,n,n-m){
    ans*=i;
  }
  FOR(i,1,m+1){
    ans/=i;
  }
  return ans;
}
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  st s;
  	ci(s);
  FOR(i,0,19){
	if(i==5||i==13)
      cout<<" ";
    else
      cout<<s[i];
  }
  cout<<" "<<endl;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!


n, y= map(int, input().split())
y /= 1000
y = int(y)

ans_i = -1
ans_j = -1
ans_k = -1

for i in range(n+1):
    if ans_i != -1:
        break
    for j in range(n+1-i):
        if n-i-j>=0 and i + j*5 + (n-i-j)*10 == y:
            ans_i = i
            ans_j = j
            ans_k = n-i-j
            break

print(ans_k, ans_j, ans_i)











Measured memory_bytes: 9108
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;
using Graph = vector<vector<int> >;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
string s;
cin>>s;
string out="";
rep(i,s.size()){
    out+="x";
}
cout<<out<<endl;
//system("pause");
return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

class Point
{
public:
    double y, x;
    Point(){
        y = x = 0.0;
    }
    Point(double y0, double x0){
        y = y0;
        x = x0;
    }
    Point(double theta){
        y = sin(theta);
        x = cos(theta);
    }
    Point operator+(const Point& p) const{
        return Point(y + p.y, x + p.x);
    }
    Point operator-(const Point& p) const{
        return Point(y - p.y, x - p.x);
    }
    Point operator*(double a) const{
        return Point(y * a, x * a);
    }
    Point operator/(double a) const{
        return Point(y / a, x / a);
    }
    double length() const{
        return sqrt(y * y + x * x);
    }
    double dist(const Point& p) const{
        return sqrt(pow(y - p.y, 2) + pow(x - p.x, 2));
    }
    double dot(const Point& p) const{
        return y * p.y + x * p.x; // |a|*|b|*cos??
    }
    double cross(const Point& p) const{
        return x * p.y - y * p.x; // |a|*|b|*sin??
    }
    double angle() const{
        return atan2(y, x);
    }
};

Point segmentsIntersection(const Point& a1, const Point& a2, const Point& b1, const Point& b2)
{
    double d = (a2 - a1).cross(b2 - b1);
    double r = (b1 - a1).cross(b2 - b1) / d;
    double s = (b1 - a1).cross(a2 - a1) / d;
    return a1 * (1.0 - r) + a2 * r;
}

double polygonArea(const vector<Point>& p)
{
    int n = p.size();
    double ret = 0.0;
    for(int i=0; i<n; ++i)
        ret += p[i].cross(p[(i+1)%n]);
    return abs(ret) / 2.0;
}

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

    Point o(0.0, 0.0);
    Point p0(0.0);
    Point p1(2.0 * M_PI / n);
    Point p2(2.0 * M_PI / n * k);
    Point p3(2.0 * M_PI / n * (1 - k));
    Point p4 = segmentsIntersection(p0, p2, p1, p3);

    vector<Point> v = {o, p0, p4, p1};
    double ans = polygonArea(v) * n;
    printf("%.10f\n", ans);

    return 0;
}

Measured memory_bytes: 3576
#include <stdio.h>
using namespace std;
constexpr int mod=1e9+7;
int main() {
  int ans=1;
  int n;
  scanf ("%d", &n);
  for (int i=1; i<=n; i++) {
    ans = (long long)ans*i%mod;
  }
  printf("%d\n", ans);
  return 0; 
}


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

int main() {
  int n;
  string s;
  cin >> n >> s;
  int cnt = 0;
  string ans  = s;
  rep(i, n) {
    if(s[i] == '(') cnt++;
    else {
      if(cnt == 0) ans = "(" + ans;
      else cnt--;
    }
  }
  ans += string(cnt, ')');
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=100005;
int p[N];
bool vis[N],mark[N];
vi v[N],ad;
void dfs(int u,int par=-1)
{
  vis[u]=true;
  ad.pb(u);
  for(int v1:v[u])
    if(!vis[v1]) dfs(v1);
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(NULL) ; cout.tie(NULL) ;
  int n,m;
  cin>>n>>m;
  rep(i,1,n+1) cin>>p[i];
  rep(i,1,m+1)
    {
      int x,y;
      cin>>x>>y;
      v[x].pb(y); v[y].pb(x);
    }
  int ans=0;
  rep(i,1,n+1)
    {
      if(vis[i]) continue;
      ad.clear();
      dfs(i);
      for(int x:ad) mark[p[x]]=true;
      for(int x:ad) if(mark[x]) ans++;
      for(int x:ad) mark[p[x]]=false;
    }
  cout<<ans<<endl;
  return 0 ;
}


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

using namespace std;

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



Measured memory_bytes: 3624
alp = ('a'..'z').to_a
a = []
a = gets.chomp.split("")
cnt = 0
if a[0] != "A"
    cnt=1
end
t = 0
u = 0
s = 0
for i in 2..a.length-2
    if a[i] == "C" && u != 1
        if t == 0
            t = 1
            s = i
        else
            u = 1
        end
    end
end
if t != 1 || u == 1
    cnt =1
end
b = 0
for i in 0..alp.length-1
    b += a.count(alp[i])
end
if a.length-b != 2
    cnt = 1
end
if cnt == 0
    puts "AC"
else
    puts "WA"
end


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

#define FOR(a,b,c) for (int a=(b);a<(c);++a)
#define REP(i,n) FOR(i,0,n)
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
#define pb push_back
#define lf double

using namespace std;

const int MAX = (int)1e6 + 5;

int main(){
	int n;
	scanf ("%d",&n);
	ll sol=0;
	FOR(i,1,n+1){
		FOR(j,1,n+1){
			if (__gcd(i,j)==1){
				sol+=n;
				continue;
			}
			int g=__gcd(i,j);
			FOR(k,1,n+1){
				int r=__gcd(g,k);
				sol+=r;
			}
		}
	}
	
	
	printf ("%lld\n",sol);
	return 0;
}


Measured memory_bytes: 3864
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    double sum = 0;
    rep(i, n) sum += 1.0 / a[i];
    double ans = 1.0 / sum;
    printf("%.10f\n", ans);
    return 0;
}


Measured memory_bytes: 256
N, M = map(int, raw_input().split())

a = []
a.append(map(int, raw_input().split()))

keylist = range(N)
colum = M
valuelist = a

A = {k: v for k, v in zip(keylist, valuelist)}


minkey = min(A, key = A.get)
minnum = min(A.values())

sum1 = 0

if minkey%(colum-1) != 0:
    sum1 = sum1 + (minkey//(colum-1))+1 
    
    
else:
    sum1 = sum1 + minkey//(colum-1)

num1 = N - minkey

if (num1-1)%(colum-1) != 0:
    sum1 = sum1 + ((num1-1)//(colum-1))+1
else: 
     sum1 = sum1 + (num1-1)//(colum-1)


print sum1

Measured memory_bytes: 11216
N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
#dp=np.zeros((N+1,3))

dp = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:
                happy =  dp[i-1][k] + S[i-1][j]
                if dp[i][j] < happy:
                    dp[i][j] = happy

print(int(max(dp[N])))

Measured memory_bytes: 56636
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
int A;
  int B;
  cin >>A>>B;

  if(A==1) {
if (B==1) {
cout <<"Draw" << endl;
}
else {
  cout << "Alice" <<endl;
}
  }
  else if ( B==1) {
cout << "Bob" << endl;
  }

  else {
if (A>B) {
cout << "Alice" << endl;
}
 else if (A==B) {
cout << "Draw" << endl;
 }
else if (A<B) {
cout << "Bob" << endl;
}
}
}
  
  

Measured memory_bytes: 256
import scala.io.StdIn._

object Main extends App {
  val Array(h, w) = readLine.split(" ").map{_.toInt}
  val canvas: List[String] = (("." * (w + 2)) +: (1 to h).map{hh => "." + readLine + "."} :+ ("." * (w + 2))).toList
  def black(x: Int, y: Int): Boolean = canvas(y).charAt(x) == '#'
  val checks = for {x <- 1 to w; y <- 1 to h} yield {
    !black(x, y) ||
    (black(x, y - 1) || black(x, y + 1) || black(x - 1, y) || black(x + 1, y))
  }

  println(if (checks.forall(identity)) "Yes" else "No")
}

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

using namespace std;

int main() {
    long long n;
    cin >> n;
    long long mini = LONG_LONG_MAX;
    for (long long i = 1; i * i <= n; i++) {
        if (((n / i) * i) == n) {
            mini = min(mini, ((n / i) + i - 2));
        }
    }
    cout << mini;
    return 0;
}


Measured memory_bytes: 256
#![allow(dead_code)]
#![allow(unused_imports)]
use ascii::{AsciiChar, AsciiStr, AsciiString};
use indexmap::IndexMap;
use itertools::*;
use libm::*;
use num::*;
use ordered_float::OrderedFloat;
use permutohedron::LexicalPermutation;
use proconio::marker::{Bytes, Chars};
use proconio::{fastout, input};
use std::cmp::{max, min, Ordering};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::mem::swap;

fn main() {
    input!(n: usize, mut a: [usize; n]);
    a.sort_by(|x, y| y.cmp(x));
    let mut ans = 0;
    for i in 1..n {
        ans += a[i / 2];
    }
    println!("{}", ans);
}


Measured memory_bytes: 6304
N = int(input())
S = list(input().split())
G = 0
P = 0
W = 0
Y = 0
for i in range(N):
    if S[i] == "G":
        G = 1
    if S[i] == "P":
        P = 1
    if S[i] == "W":
        W = 1
    if S[i] == "Y":
        Y = 1
ans = G + P + W + Y
if ans == 3:
    print("Three")
else:
    print("Four")


Measured memory_bytes: 3064
# ume 20/06/21
def dfs(s, seq, res):
  if len(s)==0: return
  for i in range(1, len(s)):
    seq.append(int(s[:i]))
    res[0] += sum(seq) + int(s[i:])
    dfs(s[i:], seq, res)
    seq.pop()
    

S = input()
seq = []
res = [int(S)]
dfs(S, seq, res)
print(res[0])

Measured memory_bytes: 9136
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        //人数
        int n = sc.nextInt();
        //基本人数
        int a = sc.nextInt();
        //海外勢の順位
        int b = sc.nextInt();
        sc.nextLine();
        
        //確定者
        int pass = 0;
        
        //海外勢の内の順位
        int rank = 1;
        
        String str = sc.nextLine();
        for(int i = 0;i < n;i++){
            //１位からの属性
            char c = str.charAt(i);
            //国内学生の場合
            if(c == 'a'){
                if(pass < a + b){
                    System.out.println("Yes");
                    pass++;
                }else{
                    System.out.println("No");
                }
            }
            
            //海外勢の場合
            if(c == 'b'){
                if(pass < a + b && rank <= b){
                    System.out.println("Yes");
                    pass++;
                    rank++;
                }else{
                    System.out.println("No");
                }
            }
            
            //それ以外の場合
            if(c == 'c'){
                System.out.println("No");
            }
        }
    }
}


Measured memory_bytes: 51848
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace kyoupuro {

    class MainClass {

        public static void Main() {
            var N = Input.NextInt();
            var A = Input.NextInt();
            var list = Input.IntList();
            var dp = new long[N + 1, N + 1, 2600]; // inputの順番, 枚数, 合計

            dp[0, 0, 0] = 1;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int sum = 0; sum <= 2500; sum++) {
                        dp[i + 1, j, sum] += dp[i, j, sum];
                        dp[i + 1, j + 1, sum + list[i]] += dp[i, j, sum];
                    }
                }
            }

            long count = 0;
            for (int i = 1; i <= N; i++) {
                count += dp[N, i, i * A];
            }
            Console.WriteLine(count);
        }
    }

    class Input {
        static IEnumerator<string> enumerator;

        public static string Line() {
            return Console.ReadLine();
        }

        public static int NextInt() {
            if (enumerator == null || !enumerator.MoveNext()) {
                enumerator = StrArr().AsEnumerable().GetEnumerator();
                enumerator.MoveNext();
            }
            return int.Parse(enumerator.Current);
        }

        public static long NextLong() {
            if (enumerator == null || !enumerator.MoveNext()) {
                enumerator = StrArr().AsEnumerable().GetEnumerator();
                enumerator.MoveNext();
            }
            return long.Parse(enumerator.Current);
        }

        public static string[] StrArr() {
            return Line().Split(' ');
        }

        public static List<int> IntList() {
            return StrArr().Select(int.Parse).ToList();
        }

        public static List<long> LongList() {
            return StrArr().Select(long.Parse).ToList();
        }

        public static void Skip(int line = 1) {
            enumerator.Reset();
            for (int i = 0; i < line; i++) Console.ReadLine();
        }

        public static void Reset() {
            enumerator.Reset();
        }
    }
}

Measured memory_bytes: 62816
#include <iostream>

using std::cin;
using std::cout;
using std::endl;

static char const *
solve(int A, int B, int C)
{
  bool check[100] = {false};
  for (int a = A % B; a != C; a = (a + A) % B)
  {
    if (check[a])
    {
      return "NO";
    }
    check[a] = true;
  }
  return "YES";
}

int
main()
{
  int A, B, C;
  cin >> A >> B >> C;
  cout << solve(A, B, C) << endl;
  return 0;
}


Measured memory_bytes: 256
//#define NDEBUG

#include <bits/stdc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define F first
#define S second
#define B back()
#define FR front()
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tiii tuple<int, int, int>
#define mt make_tuple
#define gt(t, i) get<i>(t)

//#define TEST

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

vector<ll> f(1000001);

ll inv(ll n){
    ll base = n;
    ll now = 1;
    ll t = MOD - 2;
    while(t > 0){
        if(t & 1) now = now * base % MOD;
        base = base * base % MOD;
        t >>= 1;
    }
    return now;
}

ll c(ll n, ll k){
    return f[n] * inv(f[n - k] * f[k] % MOD) % MOD;
}

int main(){
    StarBurstStream

    int n, k;
    cin >> n >> k;

    f[0] = 1;
    for(int i = 1; i <= 1000000; i++) f[i] = f[i - 1] * i % MOD;

    vector<ll> a(n);
    ll ans = 0;
    for(int i = 0; i < n; i++) cin >> a[i];

    lsort(a);

    for(int i = 0; i < n; i++){
        if(i >= k - 1){
            ans = ans + c(i, k - 1) * a[i] % MOD;
            ans %= MOD;
        }
        if(i <= n - k){
            ans = ans - c(n - i - 1, k - 1) * a[i] % MOD;
            ans %= MOD;
        }
    }

    cout << (ans % MOD + MOD) % MOD << "\n";

    return 0;
}

Measured memory_bytes: 8960
n,m = map(int,input().split())
done = 0
for i in range(1,m+1)[::-1]:
    if (m-i)&1:
        print(m+1+(m+1-i)//2,m+1+(m+1-i)//2+i)
    else:
        print((m-i)//2 + 1,(m-i)//2 + 1 + i)


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

int main(){
  int x[110];
  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n; i++){
    cin >> x[i];
  }
  int ans = 0;
  for(int i = 0; i < n; i++){
    ans += 2 * min(x[i], k - x[i]);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

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

	int A, B;
	cin >> A >> B;

	int value1 = A + B;
	int value2 = A - B;
	int value3 = A * B;

	cout << max({ value1, value2, value3 });

	return 0;
}


Measured memory_bytes: 3636
N = int(input())
MOD = 1000000000 + 7
def power_func(a, n, p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i] == "1":
            res = (res*a) % p
    return res
print(str((power_func(10, N, MOD) - 2 * power_func(9, N, MOD) + power_func(8, N, MOD)) % MOD))


Measured memory_bytes: 9168
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
    static Scanner sc ;
	public static void main (String[] args) throws java.lang.Exception
	{
	    sc = new Scanner(System.in) ;
	    int x = sc.nextInt() ;
	    while(x>0)
	    {
	        int d = x%10 ;
	        if(d==9)
	        {
	            System.out.println("Yes") ;
	            return ;
	        }
	        x/=10 ;
	    }
	    System.out.println("No") ;
	}
}


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

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define int ll
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(c) c.begin(), c.end()
#define vi vector<int>
#define pii pair<int,int>
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define MAX 500005
#define initialize(arr,elem) memset(arr,elem,sizeof(arr))

typedef long long ll;
// typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n,w;
int arr[105][105];
int memo[101][100001];
int solve(int i, int left){
	if (i<1) return 0;
	if (left==0) return 0;
	if (memo[i][left] != -1) return memo[i][left];
	if (left<arr[i][0]) return memo[i][left] = solve(i-1,left);

	return memo[i][left] = max(arr[i][1] + solve(i-1,left-arr[i][0]),solve(i-1,left));
}

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


	cin>>n>>w;
	For(i,1,n+1) cin>>arr[i][0]>>arr[i][1];
	initialize(memo,-1);
	cout<<solve(n,w);


	return 0;
}


Measured memory_bytes: 79232
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())
#define VI(a,n) vi a(n); rep(i,n)cin>>a[i];
#define sq(n) (n)*(n)

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(0);
}

signed main(){
    init();
    run();
    return 0;
}

int cnt(vi &v, int n){
    int c=0;
    rep(i,v.size())c+=(v[i]>=n-1);
    return c;
}

void run(){
    int n;
    cin>>n;
    vi e(n+1);
    REP(i,2,n){
        int t=i;
        REP(j,2,i){
            while(t%j==0){
                e[j]++;
                t/=j;
            }
        }
    }
    int ans=cnt(e,75)+cnt(e,25)*(cnt(e,3)-1)+cnt(e,15)*(cnt(e,5)-1)+cnt(e,5)*(cnt(e,5)-1)*(cnt(e,3)-2)/2;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>  
using namespace std;  
typedef long long LL;  
typedef pair<int, int> PII;  
const int MAXN = 2000 + 10, MOD = 1e9 + 7;  
int inv[MAXN];  
  
LL pm(LL a, LL n) {  
  LL r = 1;  
  for (; n; n >>= 1) {  
    if (n & 1) r = r * a % MOD;  
    a = a * a % MOD;  
  }  
  return r;  
}  
  
LL C(LL n, int m) {  
  if (m < 0 || n < 0 || n < m) return 0;  
  LL r = 1;  
  for (int i = 1; i <= m; ++ i) {  
    r = (n - i + 1) % MOD * r % MOD * inv[i] % MOD;  
  }  
  return r;  
}  
  
int main() {  
  for (int i = 1; i < MAXN; ++ i) inv[i] = pm(i, MOD - 2);  
  LL N, D, X , res = 0;  
  while(scanf("%lld%lld%lld",&N,&D,&X)==3 && N){  
   res = 0;  
   for(int i=0; i*X<=N && i <= D; i++){  
       LL xi = C(D,i);  
       LL com = C(D-1+N-i*X , N-i*X);  
       LL flag = (i&1) ? -1 : 1;  
       res = (res + flag*xi*com%MOD + MOD)%MOD;  
   }  
   printf("%d\n",(int)res);  
  }  
  return 0;  
}  

Measured memory_bytes: 3176
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int n,m;
    int num[200000];
    int num1[200000];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
        num1[i]=num[i];
    }
    sort(num1,num1+n);
    int w=num1[n/2];
    int q=num1[(n/2)-1];
    for(int i=0;i<n;i++){
        if(num[i]<=q) cout<<w<<endl;
        else cout<<q<<endl;
    }
    return 0;
}


Measured memory_bytes: 3712
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ind = [1]
    tmp = 6
    while tmp <= N:
        ind.append(tmp)
        tmp *= 6
    tmp = 9
    while tmp <= N:
        ind.append(tmp)
        tmp *= 9
    ind = sorted(ind)
    INF = int(1e9)
    dp = [INF] * (N+1)
    dp[0] = 0
    for i in range(1, N+1):
        for t in ind:
            if i - t >= 0:
                dp[i] = min(dp[i], dp[i-t]+1)
            else:
                break
    # print(dp[:20])
    print(dp[N])
    


if __name__ == "__main__":
    main()

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

int a[20000];
int b[20000];

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

	int N;
	cin >> N;

	for(int i = 0; i < N; i++) {
		a[i] = (i + 1) * 30000;
		b[i] = (N - i) * 30000;
	}

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

	for(int i = 0; i < N; i++) {
		assert(1 <= a[i] && a[i] <= 1e9);
		assert(1 <= b[i] && b[i] <= 1e9);
	}

	for(int i = 0; i < N - 1; i++) {
		assert(a[i] < a[i + 1]);
		assert(b[i] > b[i + 1]);
		//assert(a[t[i]] + b[t[i]] < a[t[i + 1]] + b[t[i + 1]]);
	}

	for(int i = 0; i < N; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	for(int i = 0; i < N; i++) {
		cout << b[i] << " ";
	}
	cout << endl;


}

Measured memory_bytes: 768
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct dice{
    int face[6];
}dice;

void rotate(dice *d, char dir)
{
    int temp;
    switch(dir) {
    case 'N':
        temp=d->face[0];
        d->face[0]=d->face[1];
        d->face[1]=d->face[5];
        d->face[5]=d->face[4];
        d->face[4]=temp;
        break;
    case 'E':
        temp=d->face[0];
        d->face[0]=d->face[3];
        d->face[3]=d->face[5];
        d->face[5]=d->face[2];
        d->face[2]=temp;
        break;
    case 'W':
        temp=d->face[0];
        d->face[0]=d->face[2];
        d->face[2]=d->face[5];
        d->face[5]=d->face[3];
        d->face[3]=temp;
        break;
    case 'S':
        temp=d->face[0];
        d->face[0]=d->face[4];
        d->face[4]=d->face[5];
        d->face[5]=d->face[1];
        d->face[1]=temp;
        break;
    }
}

int isSame(dice d1, dice d2)
{
    static const char dir[]="NNNESSSWNNNESSSWNNNESSSW";
    int i, j;
    for(i=0; i<24; i++) {
        for(j=0; j<6 && d1.face[j]==d2.face[j]; j++);
        if(j==6) return 1;
        rotate(&d2, dir[i]);
    }
    return 0;
}

int main()
{
    dice d1, d2;
    int i;
    for(i=0; i<6; i++) {
        scanf("%d", &d1.face[i]);
    }
    for(i=0; i<6; i++) {
        scanf("%d", &d2.face[i]);
    }
    puts(isSame(d1, d2)?"Yes":"No");
    return 0;
}

Measured memory_bytes: 580
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
#define SEGMAX 131072
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	ll n, odd=0, ans=1;

	bool flag=true;

	cin>>n;

	vll a(n);

	map<ll, ll> count;

	rep(i, n){
		cin>>a[i];
		count[a[i]]++;
	}

	if(n%2==0) odd++;

	for(int i=odd; i<n; i+=2){
		if(i==0){
			if(count[i]!=1){
				flag=false;
				break;
			}
		}else{
			if(count[i]!=2){
				flag=false;
				break;
			}else{
				ans=(ans<<1)%MOD;
			}
		}
	}

	if(flag){
		cout<<ans<<endl;
	}else{
		cout<<0<<endl;
	}

}


Measured memory_bytes: 4992
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3FFFFFFF
#define MN 2005
using namespace std;
priority_queue <int,vector<int>,greater<int> > q,Q;
int a[MN],pos[MN];
int n,m,p,las,ans,mn,mx;
bool u[MN];

inline int read()
{
	int n=0,f=1; char c=getchar();
	while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
	while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
	return n*f;
}

bool cmp(int x,int y) {return a[x]<a[y];}

int main()
{
	register int i,j,k;
	n=read(); m=read(); p=read();
	for (i=1;i<=n;++i) a[i]=read(),pos[i]=i;
	sort(pos+1,pos+n+1,cmp); ans=INF; u[n+1]=true;
	for (i=1;i<=n;++i)
	{
		las=0;
//		puts("sb");	
//		printf("%d %d\n",Q.size(),q.size());
		for (j=1;j<=n+1;++j)
			if (u[j])
			{
//				printf("%d %d\n",i,las);				
				for (k=1;k<=j-las-m;++k) Q.push(q.top()),q.pop();
				while (!q.empty()) q.pop(); las=j;
			}
			else q.push(a[j]);
		if (Q.size()<p) break;
		mn=Q.top(); for (j=1;j<=p;++j) mx=Q.top(),Q.pop();
		while (!Q.empty()) Q.pop();
		ans=min(ans,mx-mn);
		u[pos[i]]=true;
	}
	printf("%d",ans);
}

Measured memory_bytes: 384
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define MOD 1000000007
using namespace std;



int main(int argc, char* argv[])
{
    long n, h;
    scanf("%ld%ld", &n, &h);

    vector<long> a(n), b(n);
    long i, j;
    for(i=0; i<n; i++) {
        scanf("%ld%ld", &a[i], &b[i]);
    }
    sort(a.begin(), a.end(), greater<long>());
    sort(b.begin(), b.end(), greater<long>());
    
    vector<long> sb(n+1);
    sb[0]=0;
    for(i=0; i<n; i++) {
        sb[i+1]=sb[i]+b[i];
    }

    long min=h;
    for(i=0; i<=n; i++) {
        if(sb[i]>=h) {
            if(min>i) min=i;
        }
        else {
            long ans = i+(h-sb[i]-1)/a[0] + 1;
            if(min>ans) min=ans;
        }
    }
    printf("%ld\n", min);

    return 0;
}


Measured memory_bytes: 2560
int main(void)
{
	char str[1000];
	const char *apple = "apple";
	const char *peach = "peach";
	int i;

	gets(str);
	for (i = 0; str[i] != 0; i++){
		if (strncmp(&str[i], apple, 5) == 0){
			strncpy(str + i, peach, 5);
		}
		else if (strncmp(&str[i], peach, 5) == 0){
			strncpy(str + i, apple, 5);
		}
	}
	puts(str);

	return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {


    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);

    /////////////////////
    // Write code below /
    /////////////////////
    string c;
    cin >> c;
    if(c == "a" ||
       c == "i" ||
       c == "u" ||
       c == "e" ||
       c == "o"){
        cout << "vowel" << endl;
    } else {
        cout << "consonant" << endl;
    }
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#define INF         1e9
#define EPS         1e-9
#define REP(i,n)    for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)   for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)   for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)  for(ll i=(n);i>0;--i)
#define REPC(i,obj) for(auto i:obj)
#define R_UP(a,b)   (((a)+(b)-1)/(b))
#define ALL(obj)    (obj).begin(),(obj).end()
#define SETP        cout << fixed << setprecision(8)
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T x; cin >> x; return x; }

signed main()
{
	string inp = in<string>();
	cout << inp.find_last_of('Z') - inp.find_first_of('A') + 1 << endl;
}

Measured memory_bytes: 640
import numpy as np
from heapq import *

X, Y, Z, K = map(int, input().split())
A = [int(x) for x in  input().split()]
B = [int(x) for x in  input().split()]
C = [int(x) for x in  input().split()]

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

h = []
heappush(h, (-A[0]-B[0]-C[0], 0, 0, 0))
used = set()
result = []

for _ in range(K):
    sum, i, j, k = heappop(h)
    result.append(-sum)
    if i < X-1 and (i+1, j, k) not in used:
        heappush(h, (-A[i+1]-B[j]-C[k], i+1, j, k))
        used.add((i+1, j, k))
    if j < Y-1 and (i, j+1, k) not in used:
        heappush(h, (-A[i]-B[j+1]-C[k], i, j+1, k))
        used.add((i, j+1, k))
    if k < Z-1 and (i, j, k+1) not in used:
        heappush(h, (-A[i]-B[j]-C[k+1], i, j, k+1))
        used.add((i, j, k+1))

for v in result:
    print(v)


Measured memory_bytes: 14020
#include <cstdio>

using namespace std;

bool nok[10];

int main()
{
    #ifdef waltz
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif // waltz
    int n,k;scanf("%d%d",&n,&k);
    for (int i=1;i<=k;i++) {int x;scanf("%d",&x);nok[x]=1;}
    for (int i=n;i;i++)
    {
        int t=i;
        bool ok=1;
        while (t)
        {
            if (nok[t%10]) ok=0;
            t/=10;
        }
        if (ok) {printf("%d\n",i);break;}
    }
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(void){
    int i, ans=0, c = 3;
    char array[c+1];

    scanf( "%s", array );

    for( i=0; i<c; i++ ){
        if( array[i] == '1' ){
            ans++;
        }
    }
    
    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 128
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

		int n = sc.nextInt();
		int x = sc.nextInt();
		int z =0;
		int j=0;
		List<Integer> list=new ArrayList<Integer>();

		for(int i=0;n>i;i++) {
			int l=sc.nextInt();
			list.add(l);
		}

		while(true) {
			z=z+list.get(j);
			if(z>x) {
				break;
			}
			if(j+1==n) {
				j++;
				break;
			}
			j++;
		};

		System.out.println(j+1);

	}

}


Measured memory_bytes: 23892
use proconio::input;
use std::cmp::{max, min};

const MAX_L: u32 = 100_000;
const BASE_SIZE: usize = 1 << 10;

fn main() {
    input! {
        n: usize,
        vw: [(u32, u32); n],
        q: usize,
        vl: [(usize, u32); q],
    }
    let dp = make_dp(&vw);
    for vlq in vl {
        println!("{}", calc(&vw, vlq.0 - 1, vlq.1, &dp));
    }
}

fn make_dp(vw: &Vec<(u32, u32)>) -> Vec<Vec<u32>> {
    let mut dp = Vec::<Vec<u32>>::new();

    dp.push(
        (0..=MAX_L)
        .map(|i| if i < vw[0].1 { 0 } else { vw[0].0 })
        .collect()
    );

    let n = min(vw.len(), BASE_SIZE - 1);
    for c in 1..n {
        let p = (c - 1) / 2;
        dp.push(
            (0..=MAX_L)
            .map(|i| {
                let w = vw[c].1;
                let v = if i < w { 0 } else { dp[p][(i - w) as usize] + vw[c].0 };
                max(dp[p][i as usize], v)
            })
            .collect()
        );
    }

    dp
}

fn calc(
    vw: &Vec<(u32, u32)>,
    u: usize, 
    l: u32,
    dp: &Vec<Vec<u32>>
) -> u32 {
    if u < dp.len() {
        dp[u][l as usize]
    } else {
        let p = (u - 1) / 2;
        let w = vw[u].1;
        let pv1 = calc(vw, p, l, dp);
        let pv2 = if l < w { 0 } else { calc(vw, p, l - w, dp) + vw[u].0 };
        max(pv1, pv2)
    }
}


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

vector<Int> po(20,1);

Int dfs(Int k,Int n,Int d){
  if(k==n/2) return !d;
  Int u=po[n-(k+1)]-po[k];
  Int x=d>=0?(d+u-1)/u:d/u;
  Int res=0;
  for(Int i=0;i<2;i++,x--){
    if(x<-9||x>9) continue;
    Int v=0;
    for(Int j=(k==0);j<10;j++) v+=(0<=x+j&&x+j<10);
    res+=dfs(k+1,n,d-x*u)*v;
  }
  return res;
};

//INSERT ABOVE HERE
signed main(){
  Int d;
  cin>>d;
  for(Int i=0;i<18;i++) po[i+1]=po[i]*10;
  Int ans=0;
  for(Int i=1;i<18;i++) ans+=(i&1?1:10)*dfs(0,i+1,d);
  cout<<ans<<endl;
  return 0;
}


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

ll com(ll n){
  ll res = n*(n-1)/2;
  return res;
}

int main(void){
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> cnt(n);
  rep(i,n){
    cin >> a[i];
    cnt[a[i]]++;
  }
  ll tot = 0;
  rep(i,n) tot += com(cnt[i]);
  rep(i,n-1){
    ll ans = tot;
    ans -= com(cnt[a[i]]);
    ans += com(cnt[a[i]]-1);
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 4840
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(n);i++)
int main(){
	ll n; cin>>n;
	if(n%1000==0) cout<<0;
	else cout<<1000-n%1000;
}


Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define rep(N) for(int i=0;i<N;i++)
#define repj(N) for(int j=0;j<N;j++)
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define For(I,N) for(int I=0;I<N;I++)
#define cinone(N) int N;cin>>N;
#define scanfone(N) int N;cin>>N;
#define cinng(N,M) int N[M];for(int yiuytvnm=0;yiuytvnm<M;yiuytvnm++) cin>>N[yiuytvnm];
#define scanfng(N,M) int N[M];for(int qrwuoiq=0;qrwuoiq<M;qrwuoiq++) scanf("%d",&N[qrwuoiq]);
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
typedef unsigned long long ull;
const int inf=1039074182;
const int mod=1e9+7;
using namespace std;
char c[10005];
int dp[10005][2][105];
int k;
int n;

int main()
{
//	freopen("input.txt","r",stdin);
	scanf("%s",c);
	cin>>k;
	n=strlen(c);
	for(int i=0;i<n;i++)
	{
		c[i]-='0';
	}
	for(int i=0;i<c[0];i++)
	{
		dp[0][0][i%k]++;
	}
	dp[0][1][c[0]%k]=1;
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<=9;j++)
		{
			for(int l=0;l<k;l++)
			{
				dp[i][0][(l+j)%k]+=dp[i-1][0][l];
				dp[i][0][(l+j)%k]%=mod;
			}
		}
		for(int j=0;j<c[i];j++)
		{
			for(int l=0;l<k;l++)
			{
				dp[i][0][(l+j)%k]+=dp[i-1][1][l];
				dp[i][0][(l+j)%k]%=mod;
			}
		}
		for(int j=c[i];j<=c[i];j++)
		{
			for(int l=0;l<k;l++)
			{
				dp[i][1][(l+j)%k]+=dp[i-1][1][l];
				dp[i][1][(l+j)%k]%=mod;
			}
		}
	}
	cout<<((dp[n-1][0][0]+dp[n-1][1][0]-1)%mod+mod)%mod<<endl;
	return 0;
}

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

typedef long long ll;

void solve()
{
	int l, r, d;
	int ans = 0;
	cin >> l >> r >> d;
	for (int i = l; i <= r; i++)
	{
		if (i % d == 0)
			ans++;
	}
	cout << ans;
}

int main()
{

	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

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

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}	
	return 0;
}




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

#define times(n, i)      uptil(0, n, i)
#define rtimes(n, i)     downto((n) - 1, 0, i)
#define upto(f, t, i)    for(int i##_to_ = (t), i = (f); i <= i##_to_; i++)
#define uptil(f, t, i)   for(int i##_to_ = (t), i = (f); i <  i##_to_; i++)
#define downto(f, t, i)  for(int i##_to_ = (t), i = (f); i >= i##_to_; i--)
#define downtil(f, t, i) for(int i##_to_ = (t), i = (f); i >  i##_to_; i--)
typedef long double LD;
#define long long long

#if defined(EBUG) && !defined(ONLINE_JUDGE)
#define debug true
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 2
#define _LIBCPP_DEBUG2 2
#define ln << endl
#else
#define debug false
#define ln << '\n'
#endif
#define tb << '\t'
#define sp << ' '



signed main() { // long: 64bit
    if(!debug) {
        cin.tie(0);
        ios::sync_with_stdio(0);
    }

    int N, M; scanf("%d%d", &N, &M);

    int y = M * 1900 + (N - M) * 100;

    cout << (y << M) ln;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int n, x, l; cin >> n >> x;
	int now = 0, ans = 1;
	for (int i = 0; i < n; ++i) {
		cin >> l;
		now += l;
		if (now <= x) ans++;
	}
	cout << ans << endl;

	return 0;
}

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

struct Sieve {
  int n;
  vector<int> f, primes;
  Sieve(int n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x;}
  vector<int> factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  vector<P> factor(int x) {
    vector<int> fl = factorList(x);
    if (fl.size() == 0) return {};
    vector<P> res(1, P(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
  vector<pair<ll,int>> factor(ll x) {
    vector<pair<ll,int>> res;
    for (int p : primes) {
      int y = 0;
      while (x%p == 0) x /= p, ++y;
      if (y != 0) res.emplace_back(p,y);
    }
    if (x != 1) res.emplace_back(x,1);
    return res;
  }
};
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int n;
  cin >> n;
  Sieve s(MAX);
  vector<int> used(MAX);
  int g;
  rep(i,n) {
    int a; cin >> a;
    if (i) g = gcd(g,a);
    else g = a;
    for (auto u : s.factor(a)) used[u.first]++;
  }
  string ans = "not coprime";
  if (g==1) ans = "setwise coprime";
  bool pw = true;
  for (auto p : s.primes) if (used[p] > 1) pw = false;
  if (pw) ans = "pairwise coprime";

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 11508
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
using namespace std;
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; }
ll mod= 1e9 + 7;



int main() {
  ll a,b,c,d;
  cin >> a >>b >>c >>d;
  cout << max({a*d,a*c,b*c,b*d}) <<endl;

}

Measured memory_bytes: 3644