akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

final class Main {

    public static double cos(final int rad) {
        return Math.cos(Math.toRadians(rad));
    }

    public static double sin(final int rad) {
        return Math.sin(Math.toRadians(rad));
    }

    private Main() {
    }

    public static void main(final String[] argv) throws IOException {
        final BufferedReader inputReader =
                new BufferedReader(new InputStreamReader(System.in));

        double potisionX = 0;
        double potisionY = 0;
        int rad = 90;
        while (true) {
            final String input = inputReader.readLine();
            if (input.equals("0,0")) {
                break;
            }
            final String[] temp = input.split(",");
            potisionY += sin(rad) * Double.parseDouble(temp[0]);
            potisionX += cos(rad) * Double.parseDouble(temp[0]);
            rad -= Integer.parseInt(temp[1]);
            System.err.printf("%f/%f/%d\n", potisionX, potisionY, rad);
        }
        potisionX = potisionX >= 0 ? Math.floor(potisionX) : Math.ceil(potisionX);
        potisionY = potisionY >= 0 ? Math.floor(potisionY) : Math.ceil(potisionY);
        System.out.printf("%.0f\n", potisionX);
        System.out.printf("%.0f\n", potisionY);
    }
}

Measured memory_bytes: 11000
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE

int count(string s){
  int res = 0;
  for(int i=0;i<(int)s.size()-1;i++){
    if(s[i] == 'A' && s[i+1] == 'B') res++;
  }
  return res;
}



signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N;
  cin>>N;
  
  int ans = 0;
  int cntA = 0, cntB = 0, cntBA = 0;

  
  for(int i=0;i<N;i++){
    string s;
    cin>>s;
    ans += count(s);
    if(s[0] == 'B' && s.back() == 'A') cntBA++;
    else if(s[0] == 'B') cntB++;
    else if(s.back() == 'A') cntA++;
  }

  ans += max(0, cntBA - 1);
  if(cntBA) cntBA = 1;

  if(cntBA){
    if(cntA) ans += 1, cntA--;
    if(cntB) ans += 1, cntB--;
  }

  ans += min(cntA, cntB);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
long long tree[262144];
void add(int x,int y){
  tree[x+131070]+=y;
      int j=x+131070;
      while(j>0){
        j=(j-1)/2;
        tree[j]+=y;
}
}
int sum(int t){
  int count=0;
  int left=0;
  int right=131072;
  int j=0;
  while(right-left>1){
    int mid=(right+left)/2;
    if(t<=mid){
      right=mid;
      j=j*2+1;
    }
    else{
      count+=tree[j*2+1];
      left=mid;
      j=j*2+2;
    }
  }
    count+=tree[j];
    return count;
  }
int main(){
  for(int i=0;i<262144;i++){
    tree[i]=0;
  }
  int n,q;
  cin>>n>>q;
  for(int i=0;i<q;i++){
   int query,x,y;
    cin>>query>>x>>y;
    if(query==0){
      add(x,y);
    }
    else{
      if(x==1){
        cout<<sum(y)<<endl;
      }
      else{
      cout<<sum(y)-sum(x-1)<<endl;
      }
    }
  }
}
/*int main(){
  int n,k;
  cin>>n>>k;
  int a[100000];
  for(int i=1;i<n+1;i=i+1){
    cin>>a[i];
  }
  int answer=0;
  for(int i=1;i<k+1;i=i+1){
    answer=answer+a[i];
  }
  for(int i=2;i<n-k+2;i=i+1){
    answer=max(answer,answer-a[i-1]+a[i+k-1]);
  }
               cout<<answer<<endl;
}*/


Measured memory_bytes: 5148
import java.util.*;

class Main {


    public static void main (String [] args) {

        Scanner sc = new Scanner(System.in);

        int totalMoney = 0;
        int totalNum   = 0;
        int totalKind  = 0;

        while(sc.hasNext()) {
            String [] line = sc.nextLine().split(",");
            int m = Integer.parseInt(line[0]);
            int n = Integer.parseInt(line[1]);

            totalMoney += m * n;
            totalNum += n;
            totalKind += 1;

        }

        System.out.println(totalMoney);
        System.out.println(Math.round((totalNum + 1.0)/ totalKind));

    }
}

Measured memory_bytes: 11000
N=int(input())
table=[]
for i in range(N):
    a,b=map(int,input().split())
    table.append((a+b,a,b))
table=sorted(table,reverse=True)
t=0
ao=0
for i in range(N):
    s,a,b=table[i]
    if i%2==0:
        t+=a
    else:
        ao+=b
print(t-ao)

Measured memory_bytes: 62168
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using namespace std;
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)

int main(){
  ll h;
  cin>>h;
  ll i=1,ans=0;
  while(i<=h){
    ans+=i;
    i*=2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3632
n=int(input())
a=list(map(int,input().split()))
bina=['0'*30+bin(ai)[2:] for ai in a]
maxa=max(a)
m=len(bin(maxa))-2
ans=[0]*n
for i in range(m):
  j=-i-1
  tmp=0
  for k in range(n):
    tmp+=int(bina[k][j])
  for k in range(n):
    if tmp%2==0 and bina[k][j]=='1':
      ans[k]+=pow(2,i)
    elif tmp%2==1 and bina[k][j]=='0':
      ans[k]+=pow(2,i)
print(' '.join(map(str,ans)))


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

int main() {
  int N, M;
  int x = 0;
  int y = 0;
  
  cin >> N;
  vector<string> blue(N);
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    blue.at(i) = s;
  }
  sort(blue.begin(), blue.end());
  reverse(blue.begin(), blue.end());
  
  cin >> M;
  vector<string> red(M);
  for (int i = 0; i < M; i++) {
    string t;
    cin >> t;
    red.at(i) = t;
  }
  sort(red.begin(), red.end());
  reverse(red.begin(), red.end());

  for (int j = 0; ; ) {
    if (N > 1 && M > 0) { 
      if (blue.at(N - 1) != red.at(M - 1)) {
        if (blue.at(N - 1) > red.at(M - 1)) {
          red.pop_back();
          M--;
        }
        else {
          if (blue.at(N - 1) == blue.at(N - 2)) { 
          blue.pop_back();
          N--;
          x++;
          }
          else {
            blue.pop_back();
            N--;
            x++;
            if (x > y) {
            y = x;
            }
            x = 0;
          }        
        }
      }
      
      else if (blue.at(N - 1) == red.at(M - 1)) { 
        if (blue.at(N - 1) == blue.at(N - 2)) {
          blue.pop_back();
          red.pop_back();
          N--;
          M--;
        }
        else {
          blue.pop_back();
          red.pop_back();
          N--;
          M--;
          if (x > y) {
            y = x;
          }
          x = 0;
        }
      }
    }
    
    else if (N > 1 && M == 0) 
      if (blue.at(N - 1) == blue.at(N - 2)) {
        blue.pop_back();
        N--;
        x++;
      }
      else {
        blue.pop_back();
        N--;
        x++;
          if (x > y) {
            y = x;
          }
        x = 0;
      }
    
    else if (N == 1 && M == 0) {
      x++;
      if (x > y) {
        y = x;
      }
      x = 0;
      break;
    }
    
    else if (N == 1 && M > 0) { 
      if (M > 1 && blue.at(N - 1) != red.at(M - 1)) {
        M--;
      }
      else if (M == 1 && blue.at(N - 1) != red.at(M - 1)) {
        x++;
        if (x > y) {
            y = x;
          }
        x = 0;
        break;
      }
      else if (blue.at(N - 1) == red.at(M - 1)) {
        if (x > y) {
          y = x;
          }
        x = 0;
        break;
      }
    }
  }
  cout << y << endl;
}

Measured memory_bytes: 3628
module mod1
implicit none
integer(8) :: par(0:200000),count(0:200000)=0,kodomo(0:200000)=1,temp1,temp2,temp3
end module mod1

program test
use mod1 
implicit none

integer(8) :: n,q,i,j,k,m
integer(8) :: p(0:200000),a(0:200000),b(0:200000)

read(*,*) n,m
do i=m,1,-1
	read(*,*) a(i),b(i)
enddo

!親の番号
do i=0,n
	par(i) = i
enddo

do i=1,m
	if(root(a(i)) .eq. root(b(i)))then
		count(i) = count(i-1)
		continue
	else
		!子、親
		temp1 = (kodomo(root(b(i)))+kodomo(root(a(i))))*(kodomo(root(b(i)))+kodomo(root(a(i)))-1)/2
		temp2 = (kodomo(root(a(i))))*(kodomo(root(a(i)))-1)/2
		temp3 = (kodomo(root(b(i))))*(kodomo(root(b(i)))-1)/2
		count(i) = count(i-1) + temp1 - temp2 - temp3
		kodomo(root(b(i))) = kodomo(root(b(i))) + kodomo(root(a(i)))
		kodomo(root(a(i))) = 1
		call unite(a(i),b(i))
	endif
enddo

do i=m-1,0,-1
	write(*,*) count(m) - count(i)
enddo

contains
recursive function root(x) result(res)
integer(8) :: x,res
	if(par(x) == x) then
		continue
	else
		par(x) = root(par(x))
	endif
	res = par(x)
end function

subroutine unite(x,y)
integer(8) :: x,y
x = root(x)
y = root(y)
if(x .ne. y) then
	par(x) = y
endif
end subroutine


end program

Measured memory_bytes: 8576
N = int(input())
sqrt_N = int(N ** 0.5)

dividers_for_N = []
ans_list = []

for i in range(1, sqrt_N + 1):
    if (N - 1) % i == 0:
        ans_list.append(i)
        if i != (N - 1) // i:
            ans_list.append((N - 1) // i)

    if N % i == 0:
        dividers_for_N.append(i)
        if i != N // i:
            dividers_for_N.append(N // i)

dividers_for_N.remove(1)
ans_list.remove(1)
        
for i in dividers_for_N:
    num = N
    while num % i == 0:
        num //= i
    if num % i == 1:
        ans_list.append(i)

ans = len(ans_list)

print(ans)

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pair2;
typedef pair<int, pair<int, int> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 2000013
#define INF 1000000000000000000LL
#define MOD 1000000007LL
#define IINF 1000000000
#define mp make_pair
#define pb push_back
#define remove pop
#define all(x) x.begin(), x.end()


ll fact[MAXN];
ll factInv[MAXN];

ll modpow(ll a, ll b) {
    ll res = 1;
    for (; b > 0; b >>= 1) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}


ll modInverse(ll a) {
	return modpow(a, MOD - 2);
}


void getFactorials(int maxFact) {
	fact[0] = 1;

	for (int i = 1; i <= maxFact; i++) {
		fact[i] = fact[i - 1] * i;
		fact[i] %= MOD;
	}

	for (int i = 0; i <= maxFact; i++) {
		factInv[i] = modInverse(fact[i]);
	}
}

ll normalize(ll a) {
	return (((a % MOD) + MOD) % MOD);
}


int main() {
	if (fopen("FILENAME.in", "r")) {
		freopen("FILENAME.in", "r", stdin);
		freopen("FILENAME.out", "w", stdout);
	}
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	int x, y;
	cin >> x >> y;

	int total = x + y;

	if (total % 3 != 0) {
		cout << 0 << endl;
		return 0;
	}

	int length = total / 3;

	int curx = 2 * length;
	int cury = length;

	bool satisfied = false;
	int satIndex = -1;

	for (int i = 0; i <= length; i++) {
		//Assume this length of i + 1, j + 2 moves

		if (curx == x && cury == y) {
			satisfied = true;
			satIndex = i;
			break;
		}

		curx--;
		cury++;
	}

	if (!satisfied) {
		cout << 0 << endl;
		return 0;
	}

	getFactorials(length + 10);

	//cout << "Length is " << length << endl;
	fact[0] = 1;

	//cout << "fact is " << fact[length] << " and opposite is " << fact[satIndex] * fact[length - satIndex] << endl;
	cout << normalize(fact[length] * modInverse(normalize(fact[satIndex] * fact[length - satIndex]))) << endl;
}

//GCD GCD GCD USE GCD IN MATH

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

int main(){
    ll x,y;
    cin >> x >> y;
    
    ll save=x;
    int ans=1;
    while(1){
        if(save*2<=y){
            save=save*2;
            ans++;
        }
        else break;
    }

    printf("%d",ans);
}

Measured memory_bytes: 256
use proconio::input;
use std::cmp::max;
use std::cmp::min;

fn main() {
    input! {
        w: usize,
        h: usize,
        n: usize,
        xya: [[usize; 3]; n],
    }

    solve(w, h, n, &xya);
}

fn solve(w: usize, h: usize, n: usize, xya: &Vec<Vec<usize>>) {
    let mut min_x = 0;
    let mut max_x = w;
    let mut min_y = 0;
    let mut max_y = h;

    for i in 0..n {
        match xya[i][2] {
            1 => min_x = max(min_x, xya[i][0]),
            2 => max_x = min(max_x, xya[i][0]),
            3 => min_y = max(min_y, xya[i][1]),
            4 => max_y = min(max_y, xya[i][1]),
            _ => {}
        }
    }

    if min_x >= max_x {
        println!("0");
        return;
    }
    if min_y >= max_y {
        println!("0");
        return;
    }

    println!("{}", (max_x - min_x) * (max_y - min_y));
}


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

ll g1(ll n, int p) {
  if (n == 0) return 0;
  return n / p + g1(n / p, p);
}

ll g2(ll n, int p) {
  if (n % 2 == 1) {
    return g1(n, p) - g2(n - 1, p);
  } else {
    ll res = g1(n / 2, p);
    if (p == 2) res += n / 2;
    return res;
  }
}

int main() {
  ll n;
  cin >> n;

  ll ans = min(g2(n, 2), g2(n, 5));
  cout << ans << endl;
  return 0;
}

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

int main(){
  string s;
  cin >> s;
  
  int c = 0;
  for(int i=0; i<s.size(); i++){
    if(s.at(i) == '1'){
      c++;
    }
  }
  
  cout << c;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template <typename T> using vec = vector<T>;

int main()
{
    long n,d;
    cin >> n >> d;
    long x[n], y[n];
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (x[i]*x[i] + y[i]*y[i] <= d*d)
        {
            ans++;
        }
        
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 6744
#include<bits/stdc++.h>
#define N 100100
using namespace std;
int dep[N];
vector<int> g[N];
bool cmp(int a,int b){
	return dep[a]>dep[b];
}
int DFS(int u){
	if(g[u].empty()) return dep[u]=0;
	for(int i=0;i<g[u].size();i++) DFS(g[u][i]);
	sort(g[u].begin(),g[u].end(),cmp);
	for(int i=0;i<g[u].size();i++){
		dep[u]=max(dep[u],dep[g[u][i]]+i+1);
	}
	return dep[u];
}
int main(){
	int n,x;
	scanf("%d",&n);
	for(int i=2;i<=n;i++) scanf("%d",&x),g[x].push_back(i);
	printf("%d\n",DFS(1));
	return 0;
}

Measured memory_bytes: 10752
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<list>

#define endl "\n"
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define REP(i, n) for(int i = 0; i < n; i++)
using Graph = vector<vector<int>>;

int main(){
    int n;
    cin>>n;
    string s;
    map<string,int> memo;
    for(int i=0;i<n;i++){
        cin>>s;
        memo[s]++;
    }

    int smax = 0;
    for(auto x : memo){
        smax = max(smax, x.second);
    }
    for(auto x : memo){
        if(x.second == smax) cout<<x.first<<endl;
    }
}

Measured memory_bytes: 25216
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int H1 = sc.nextInt();
		int M1 = sc.nextInt();
		int H2 = sc.nextInt();
		int M2 = sc.nextInt();
		int K = sc.nextInt();
		
		System.out.println((H2*60+M2)-(H1*60+M1)-K);
		
		sc.close();
	}
	
}


Measured memory_bytes: 27004
mod = 998244353
N, A, B, K = [int(_) for _ in input().split()]


def extgcd(a, b):
    if b:
        x, y = extgcd(b, a % b)
        x, y = y, x - (a // b) * y
    else:
        x, y = 1, 0
    return x, y


E = extgcd(A, B)
g = A * E[0] + B * E[1]
l = A * B // g
F = [E[0] * (K // g), E[1] * (K // g)]
if F[0] > F[1]:
    F = F[::-1]
    A, B = B, A
H = [F[0] + B * (F[1] // A), F[1] - A * (F[1] // A)]
L = []
for i in range(-100000, max(H[0] // (B // g), H[1] // (A // g)) + 100000):
    J = [H[0] - (B // g) * i, H[1] + (A // g) * i]
    if 0 <= J[0] <= N and 0 <= J[1] <= N:
        L += [J]
f = [1] * (N + 1)
for i in range(2, N + 1):
    f[i] = f[i - 1] * i % mod
fi = [pow(f[-1], mod - 2, mod)]
for i in range(N, 0, -1):
    fi += [fi[-1] * i % mod]
fi = fi[::-1]


def comb(x, y):
    return (f[x] * fi[y] * fi[x - y]) % mod


ans = 0
for pq in L:
    p, q = pq
    ans += comb(N, p) * comb(N, q)
    ans %= mod
print(ans)


Measured memory_bytes: 67064
import java.util.*;
public class Main {

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      int a = sc.nextInt();
      int b = sc.nextInt();
      int x = sc.nextInt();
      if(a > x || b < x - a)
        System.out.println("NO");
      else
        System.out.println("YES");
  }
}

Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        /* 
        Ofcourse it's Hard.
        It's supposed to be Hard.
        If it's easy everyone would do it.
        HARD IS WHAT MAKES IT GREAT

        YESTERDAY U SAID TOMORROW

        SLOWLY BECOMING THE PERSON I 
        SHOULD HAVE BEEN A LONG TIME AGO

        SAME TASK CAN'T BE FOUND DIFFICULT TWICE

        BTBHWSITW

        SPRH TU KAB P

        CP IS ALL ABOUT THINKING 
        YOU HAVE MUCH MORE POTENTIAL THAN U THINK

        AJIT SHIDDAT 10

        UR DAILY ROUTINE 


        */

fast();
//ll t;cin>>t;while(t--)
{
    ll a,b,c=0;
    cin>>a>>b;
    if(a<b)
        swap(a,b);
    c+=a;
    a--;
    if(a<b)
        swap(a,b);
    c+=a;
    cout<<c<<endl;


}
return 0;
}

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

int N, Q;
lint D;
vector<lint> d;
vector<int> q;

vector<lint> x;
vector<int> ok;

int main()
{
    cin >> N >> D;
    d.resize(N);
    for (auto &v : d) cin >> v;
    cin >> Q;
    q.resize(Q);
    for (auto &v : q) cin >> v;

    x.resize(N);
    x[0] = D;
    for (int i = 1; i < N; i++) x[i] = min(x[i-1], abs(x[i-1] - d[i-1]));

    ok = vector<int>(N, 0);

    lint w = 1;
    for (int i = N - 1; i >= 0; i--)
    {
        // cout << x[i] << " " << w << endl;
        ok[i] = (x[i] >= w) ? 0 : 1;
        if (d[i] >= 2 * w)
        {
            ;
        }
        else
        {
            w += d[i];
        }
    }
    for (auto v : q)
    {
        if (ok[v-1]) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
}


Measured memory_bytes: 15232
// 2014/07/25 Tazoe

#include <iostream>
#include <cctype>
using namespace std;

int main()
{
	int cnt[26] = {0};

	while(true){
		char c;
		cin >> c;

		if(cin.eof())
			break;

		if(islower(c)){
			cnt[c-'a']++;
		}
		else if(isupper(c)){
			cnt[c-'A']++;
		}
	}

	for(int i=0; i<26; i++){
		cout << (char)(i+'a') << " : " << cnt[i] << endl;
	}

	return 0;
}

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

void chmin(int& a, int b){
    a = min(a, b);
}

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

int main(){
    int N, Ma, Mb, a[40], b[40], c[40];
    cin >> N >> Ma >> Mb;
    for(int i=0; i<N; i++) cin >> a[i] >> b[i] >> c[i];

    // OFFSETはsが負になることを防ぐために足す値
    const int OFFSET = 2000, INF = 1e9;
    
    // C[g][s] = グループgの選び方（1つ以上）で Mb*sumA - Ma*sumB + OFFSET = s となるときの最小コスト
    int C[2][4001];
    for(int g=0; g<2; g++) for(int s=0; s<=4000; s++) C[g][s] = INF;
    
    // グループgに属するのはインデックス [start[g], term[g]) の範囲のものとする
    int start[2] = {0, N/2}, term[2] = {N/2, N};
    
    for(int g=0; g<2; g++){
        int sz = term[g] - start[g];
        // 全列挙。1つ以上選ぶのでbits=0を見ない
        for(int bits=1; bits<(1<<sz); bits++){
            int s = OFFSET, cost = 0;
            for(int i=0; i<sz; i++) if(nth_bit(bits, i)){
                s += Mb * a[i+start[g]] - Ma * b[i+start[g]];
                cost += c[i+start[g]];
            }
            chmin(C[g][s], cost);
        }
    }

    // C[0][0], C[1][0], C[0][s] + C[1][-s] をそれぞれ調べるが、OFFSETに注意
    int ans = min(C[0][OFFSET], C[1][OFFSET]);
    for(int s=0; s<=4000; s++) chmin(ans, C[0][s] + C[1][2*OFFSET-s]);
    if(ans >= INF) ans = -1;
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define int long long
#define FR first
#define SC second
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, f, n) for(int i = (int)(f); i < (int)(n); i++)
#define each(a, b) for(auto& a : b)

typedef pair<int, int> P;

const int inf = 1LL << 55;

struct Dinic
{
  struct edge
  {
    int to, cap, rev;
    edge(){}
    edge(int to, int cap, int rev):to(to), cap(cap), rev(rev){}
  };

  vector< vector<edge> > graph;
  vector<int> level, iter;

  Dinic(int V):graph(V), level(V), iter(V){}
  
  pair<int, int> add_edge(int f, int t, int cap, bool bi = false)
  {
    graph[f].push_back(edge(t, cap, graph[t].size()));
    graph[t].push_back(edge(f, (bi ? cap : 0), graph[f].size()-1));
    return make_pair(graph[f].size()-1, graph[t].size()-1);
  }
  void bfs(int s)
  {
    fill(all(level), -1);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()) {
      int v = que.front(); que.pop();
      for(edge& e : graph[v]) {
	if(e.cap > 0 && level[e.to] < 0) {
	  level[e.to] = level[v] + 1;
	  que.push(e.to);
	}
      }
    }
  }
  int dfs(int v, int t, int f)
  {
    if(v == t) return f;
    for(int &i = iter[v]; i < graph[v].size(); i++) {
      edge& e = graph[v][i];
      if(e.cap > 0 && level[v] < level[e.to]) {
	int d = dfs(e.to, t, min(f, e.cap));
	if(d > 0) {
	  e.cap -= d;
	  graph[e.to][e.rev].cap += d;
	  return d;
	}
      }
    }
    return 0;
  }
  int max_flow(int s, int t, int exf = inf)
  {
    int flow = 0;
    while(exf) {
      bfs(s);
      if(level[t] < 0) return flow;
      fill(all(iter), 0);
      int f;
      while(exf && (f = dfs(s, t, exf)) > 0) flow += f, exf -= (exf != inf);
    }
    return flow;
  }
};

int N, E, Q;
vector< tuple<int, int, int> > query;
int conn[505][505];

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> N >> E >> Q;
  Dinic graph(N);
  memset(conn, -1, sizeof(conn));
  while(E--) {
    int f, t;
    cin >> f >> t; f--, t--;
    tie(conn[f][t], conn[t][f]) = graph.add_edge(f, t, 1, true);
  }
  while(Q--) {
    int m, a, b;
    cin >> m >> a >> b; a--, b--;
    query.emplace_back(m, a, b);
    if(m == 1 && !~conn[a][b]) {
      tie(conn[a][b], conn[b][a]) = graph.add_edge(a, b, 0, true);
    }
  }

  int s = 0, t = N-1; 
  int mxf = graph.max_flow(s, t);
  
  for(auto q : query) {
    int m, a, b;
    tie(m, a, b) = q;
    if(m == 1) {
      graph.graph[a][conn[a][b]].cap = graph.graph[b][conn[b][a]].cap = 1;
      mxf += graph.max_flow(0, N-1);
    } else if(m == 2) {
      int cap = graph.graph[a][conn[a][b]].cap;
      graph.graph[a][conn[a][b]].cap = graph.graph[b][conn[b][a]].cap = 0;
      // cap == 1 : didn't use
      if(cap == 0) { // used a -> b
	if(!graph.max_flow(a, b, 1)) {
	  graph.max_flow(t, b, 1);
	  graph.max_flow(a, s, 1);
	  mxf--; 	  
	}
      } else if(cap == 2) { // used b -> a
	if(!graph.max_flow(b, a, 1)) {
	  graph.max_flow(t, a, 1);
	  graph.max_flow(b, s, 1);
	  mxf--; 	  
	}
      }
    }
    cout << mxf << endl;
  }
  
  return 0;
}

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

int main() {
    int n; cin >> n;
    string s; cin >> s;
    int ans = 0;
    rep(i,n-2) {
        if (s.substr(i,3) == "ABC") ans ++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1<<30;
int main(){
	string s;
	cin>>s;
	bool h=true;
	while(s!="ABC"){
		if(s.size()<=3){
			h=false;
			break;
		}
		int co[3]={0};
		rep(i,s.size())co[s[i]-'A']++;
		int c=0;
		rep(i,s.size()-2)if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C')c++;
		if(c==0){
			h=false;
			break;
		}
		rep(i,4){
			if(i==3){
				s="ABC";
				h=false;
				break;
			}
			if(co[i]==c){
				string t;
				rep(j,s.size()){
					if(j<s.size()-2&&s[j]=='A'&&s[j+1]=='B'&&s[j+2]=='C'){
						j+=2;
						t+=(char)('A'+i);
					}else t+=s[j];
				}
				s=t;
				break;
			}
		}
	}
	if(h)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Measured memory_bytes: 1220
#define _USE_MATH_DEFINES
#include <math.h>
#include <time.h>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <typeinfo>

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 PI M_PI
#define INF 1000000000
#define MOD 1000000007;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<bool>> vvb;
typedef vector<vector<string>> vvs;

constexpr int dir[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };



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


	cout << (X - A)%- B << endl;
	


	return 0;
}


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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define yes "Yes"
#define no "No"

typedef pair<int, int> P;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    vector<int> a(n);
    REP(i,n) cin>>a[i];
    sort(all(a));
    print(a[n-1]-a[0]);
    return 0;
}

Measured memory_bytes: 256
//https://atcoder.jp/contests/dp/tasks/dp_j

#include <bits/stdc++.h>
#include <limits.h>
#include <algorithm>  


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

typedef long long int ll;

const int precision = 16;
const int modulo =  1000000007; // 10^9 + 7
using ll = long long;
const double EPS = 1e-9;

const int nax = 305;
double p[nax][nax][nax]; // probability of getting to state abc.
double ev[nax][nax][nax];


double solveSushi() {
	int n; cin >> n;
	
	vector<int> cnt(4);
	for(auto i = 0; i < n; ++i) {
		int v; cin >> v;
		++cnt[v];
	}
	
	p[cnt[1]][cnt[2]][cnt[3]] = 1;

	for(int c = n; c >= 0; c--) { //3 
		for(int b = n; b >= 0; b--) { // 2
			for(int a = n; a >= 0; --a) { //1
				if(a == 0 and b == 0 and c == 0) { 
					continue;
				}

				if((a + b + c) > n) {
					continue;
				}

				double pWaste = (double) (n - (a + b + c)) / n;
				//pWaste + pWaste^2 + ... = S
				// 1 + S = S / pWAste  
				double evWaste = pWaste / (1 - pWaste) + 1;

				ev[a][b][c] += evWaste * p[a][b][c];

				//remove 1 -> dp[a - 1][b][c]
				// we will eventually choose one of a + b + c

				if(a != 0) {
					double p_go = (double) a / (a + b + c);
					p[a - 1][b][c] += p[a][b][c] * p_go;
					ev[a - 1][b][c] += ev[a][b][c] * p_go;
				}

				//remove 2 -> dp[a + 1][b - 1][c]
				if(b != 0) {
					double p_go = (double) b / (a + b + c);
					p[a + 1][b - 1][c] += p[a][b][c] * p_go;
					ev[a + 1][b - 1][c] += ev[a][b][c] * p_go;
				}

				//remove 3 -> dp[a][b + 1][c - 1]

				if(c != 0) {
					double p_go = (double) c / (a + b + c);
					p[a][b + 1][c - 1] += p[a][b][c] * p_go;
					ev[a][b + 1][c - 1] += ev[a][b][c] * p_go;
				}
			}
		}
	}

	return ev[0][0][0];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(precision);
	cout.setf(ios_base::fixed);

	
	double ret = solveSushi();
	cout << ret << endl;
	return 0;
}



Measured memory_bytes: 438528
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<queue>
const int mod = 1e9 + 7;
using namespace std;
typedef long long ll;


int main()
{
    int n;
    cin >> n;
    int a[n];
    int b[n];
    int s = 0, ans = 1;
    bool can = true;
    for(int i = 0; i < n; i++){
        b[i] = 0;
    }
    if(n % 2 == 0){
        for(int i = 0; i < n; i++){
            cin >> a[i];
            if(a[i] % 2 == 0){
                can = false;
            }
            b[a[i]]++;
        }
        for(int i = 0; i < n; i++){
            if(b[i] > 2){
                can = false;
            }else if(b[i] == 2){
                s++;
            }
        }
    }else{
        for(int i = 0; i < n; i++){
            cin >> a[i];
            if(a[i] % 2 == 1){
                can = false;
            }
            b[a[i]]++;
        }
        for(int i = 0; i < n; i++){
            if(b[i] > 2){
                can = false;
            }else if(b[i] == 2){
                s++;
            }
        }
        if(b[0] == 2){
            can = false;
        }
    }
    for(int i = 0; i < s; i++){
        ans *= 2;
        ans %= mod;
    }
    if(can){
        cout << ans << endl;
    }else{
        cout << 0 << endl;
    }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

struct mint {
    lint v;
    lint _mod;
    mint() : v(0) {}
    mint(signed v, lint _mod = mod) : v(v), _mod(_mod) {}
    mint(lint t, lint _mod = mod) : _mod(_mod) {
        v = t % _mod;
        if (v < 0)
            v += _mod;
    }

    mint pow(lint k) {
        mint res(1), tmp(v);
        while (k) {
            if (k & 1)
                res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    static mint add_identity() { return mint(0); }
    static mint mul_identity() { return mint(1); }
    mint inv() { return pow(_mod - 2); }

    mint &operator+=(mint a) {
        v += a.v;
        if (v >= _mod)
            v -= _mod;
        return *this;
    }
    mint &operator-=(mint a) {
        v += _mod - a.v;
        if (v >= _mod)
            v -= _mod;
        return *this;
    }
    mint &operator*=(mint a) {
        v = v * a.v % _mod;
        return *this;
    }
    mint &operator/=(mint a) { return (*this) *= a.inv(); }

    mint operator+(mint a) const { return mint(v) += a; };
    mint operator-(mint a) const { return mint(v) -= a; };
    mint operator*(mint a) const { return mint(v) *= a; };
    mint operator/(mint a) const { return mint(v) /= a; };

    mint operator-() const { return v ? mint(_mod - v) : mint(v); }

    bool operator==(const mint a) const { return v == a.v; }
    bool operator!=(const mint a) const { return v != a.v; }
    bool operator<(const mint a) const { return v < a.v; }
};
ostream &operator<<(ostream &os, mint m) { return os << m.v; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint n, a, b;
    cin >> n >> a >> b;
    mint ret  = mint(2).pow(n) - 1;
    mint numa = 1, numb = 1;
    for (lint i = 0; i < a; ++i) {
        numa *= n - i;
        numa /= (i + 1);
    }
    for (lint i = 0; i < b; ++i) {
        numb *= n - i;
        numb /= (i + 1);
    }
    ret -= numa;
    ret -= numb;
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 384
n, k = map(int, input().split())
a = list(map(int, input().split()))
keta_a = [0]*41
bin_k = format(k, 'b').zfill(41)
for i in a:
  bin_a = str(format(i, 'b'))
  for j in range(len(bin_a)):
    if bin_a[-j-1] == '1':
      keta_a[-j-1]+=1
dp = [[0]*2 for _ in range(41)] #dp[i桁目まで決めた][smaller flag(0ならKと同じ, 1ならKより小さいことが確定)]
flag = True
for i in range(1, 41):
  if flag:
    if bin_k[i] == '0':
      dp[i][0] = dp[i-1][0]+2**(40-i)*keta_a[i]
    if bin_k[i] == '1':
      flag = False
      dp[i][0] = dp[i-1][0]+2**(40-i)*(n-keta_a[i])
      dp[i][1] = dp[i-1][0]+2**(40-i)*keta_a[i]
  else:
    if bin_k[i] == '0':
      dp[i][0] = dp[i-1][0]+2**(40-i)*keta_a[i]
      dp[i][1] = dp[i-1][1] + 2**(40-i)*max(n-keta_a[i], keta_a[i])
    if bin_k[i] == '1':
      dp[i][0] = dp[i-1][0] + 2**(40-i)*(n-keta_a[i])
      dp[i][1] = max(dp[i-1][0] + 2**(40-i)*(keta_a[i]),dp[i-1][1] + 2**(40-i)*max(n-keta_a[i], keta_a[i]))
print(max(dp[40][0], dp[40][1]))

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

signed main() {
  int n,k; cin>>n>>k;
  vector<int> candles(n);
  rep(i,n) cin>>candles[i];
  int ans = 1e9;
  rep(i,n-k+1) {
    int left = candles[i];
    int right = candles[i+k-1];
    if ((left>=0&&right>=0) || (left<=0&&right<=0)) {
      int cost = max(abs(left), abs(right));
      ans = min(ans, cost);
    } else {
      int cost = max(abs(left), abs(right)) + min(abs(left), abs(right))*2;
      ans = min(ans, cost);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
x = int(input())
if x <= 599:
    print(8)
elif x <=799:
    print(7)
elif x <= 999:
    print(6)
elif x <= 1199:
    print(5)
elif x <= 1399:
    print(4)
elif x <= 1599:
    print(3)
elif x <= 1799:
    print(2)
elif x <= 1999:
    print(1)

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

int get(vector<vector<int>> &v,int x1,int y1,int x2,int y2){
    return v[x2][y2]+v[x1][y1]-v[x2][y1]-v[x1][y2];
}

int main(){
    int n,d;
    cin>>n>>d;
    vector<vector<int>>cnt(d,vector<int>(d));
    rep(i,n){
        int x,y;
        cin>>x>>y;
        cnt[x%d][y%d]++;
    }
    int ma=0;
    rep(i,d)rep(j,d){
        int rt=sqrt(cnt[i][j]);
        if(rt*rt<cnt[i][j])++rt;
        ma=max(rt,ma);
    }
    vector<vector<int>> sum1(2*d+2,vector<int>(2*d+2)),sum2(2*d+2,vector<int>(2*d+2));
    int tot1=0,tot2=0;
    rep(i,d)rep(j,d){
        if(cnt[i][j]>ma*(ma-1)){
            ++sum1[i][j],
            ++sum1[i+d][j],
            ++sum1[i][j+d],
            ++sum1[i+d][j+d],
            ++tot1;
        }
        else if(cnt[i][j]>(ma-1)*(ma-1)){
            ++sum2[i][j],
            ++sum2[i+d][j],
            ++sum2[i][j+d],
            ++sum2[i+d][j+d],
            ++tot2;
        }
    }
    rep(i,2*d)rep(j,2*d){
        sum1[i+1][j]+=sum1[i][j];
        sum2[i+1][j]+=sum2[i][j];
    }
    rep(i,2*d)rep(j,2*d){
        sum1[i][j+1]+=sum1[i][j];
        sum2[i][j+1]+=sum2[i][j];
    }

    int ok=d,ng=0,mid;
    while(ok-ng>1){
        mid=(ok+ng)/2;
        bool can=false;
        rep(i,d)rep(j,d){
            if(get(sum1,i,j,i+mid,j+mid)==tot1&&
            get(sum2,i+mid,j+mid,i+d,j+d)==0){
                can=true;
                break;
            }
        }
        if(can)ok=mid;
        else ng=mid;
    }

    cout<<(ma-1)*d+ok-1 <<endl;
}


Measured memory_bytes: 35584
#include <stdio.h>

int main(void)
{
    int a[100][100]; 
    int b[100]; 
    int n, m, i, j;
    int sum;

    scanf("%d %d", &n, &m);

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

    for (i = 0; i < m; i++){
        scanf("%d", &b[i]);
    }

    for (i = 0; i < n; i++){
        sum = 0;
        for (j = 0; j < m; j++){
            sum += a[i][j] * b[j];
        }

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

    return (0);

}



Measured memory_bytes: 2112
H, W = map(int, input().split())
S = [0]*H
for i in range(H):
  S[i] = input()
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      check = []
      try:
        check.append(S[i-1][j])
      except:
        check.append('.')
      try:
        check.append(S[i][j-1])
      except:
        check.append('.')
      try:
        check.append(S[i+1][j])
      except:
        check.append('.')
      try:
        check.append(S[i][j+1])
      except:
        check.append('.')
      if '#' not in check:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 3064
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <math.h>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

#define ll long long
#define ull unsigned long long

#define	max	1000000007

ll gcd(ll a, ll b) {
	if (a < b)
		swap(a, b);
	while (ll r = a % b)
		a = b, b = r;
	return b;
}

ll combi(ll n, ll k)
{
	if (k >= n || k <= 0)
		return 1;
	ll r = 1;
	for (ll i = 1; i <= k; i++, n--)
		r *= n, r /= i;
	return r;
}

class mod
{
public:
	ll val;

	mod(ll v)
	{
		val = v % max;
	}

	mod()
	{
		val = 0;
	}

	void operator -=(const mod &v)
	{
		val -= v.val;

		if (val < 0)
			val += max;
	}

	void operator +=(const mod &v)
	{
		if (val + v.val >= max)
			val -= max;
		val += v.val;
	}

	void operator +=(ll &v)
	{
		if (val + v >= max)
			val -= max;
		val += v;
	}

	void operator *=(const mod &v)
	{
		val *= v.val;
		val %= max;
	}

	void operator *=(ll &v)
	{
		val *= v;
		val %= max;
	}

	ll modinv(ll a)
	{
		ll b = max, u = 1, v = 0;
		while (b)
		{
			ll t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= max;
		if (u < 0)
			u += max;
		return u;
	}

	void operator /=(const mod &v)
	{
		val *= modinv(v.val);
		val %= max;
	}

	void operator /=(ll &v)
	{
		val *= modinv(v);
		val %= max;
	}
};

struct magic
{
	int a, b;
	float c;
};

int main()
{
	int h, n;
	cin >> h >> n;
	vector<magic> m(n);
	for (int i = 0; i < n; i++)
	{
		cin >> m[i].a >> m[i].b;
		m[i].c = (float)m[i].a / m[i].b;
	}

	sort(m.begin(), m.end(), [](const magic &l, const magic &r) {return l.c > r.c; });
	
	vector<vector<long>> dp(h + 1, vector<long>(n + 1, 0));

	for (int H = 1; H <= h; H++)
		dp[H][1] = ((H % m[0].a != 0 ? 1 : 0) + H / m[0].a) * m[0].b;
	for (int N = 1; N < n; N++)
		for (int H = 1; H <= h; H++)
		{
			long tmp = dp[H - m[N].a < 0 ? 0 : H - m[N].a][N + 1] + m[N].b;
			dp[H][N + 1] = tmp < dp[H][N] ? tmp : dp[H][N];
		}

	printf("%ld", dp[h][n]);

	return 0;
}


Measured memory_bytes: 78848
n,l=map(int,input().split())
dic={0:0}
for _ in range(n):
  w,v=map(int,input().split())
  tmp=sorted(list(dic.keys()),reverse=True)
  for key in tmp:
    if key+w not in dic:
      dic[key+w]=dic[key]+v
    else:
      dic[key+w]=max(dic[key]+v,dic[key+w])
tmp=sorted(list(dic.keys()))
ans=0
for key in tmp:
  if key>l:
    break
  ans=max(ans,dic[key])
print(ans)


Measured memory_bytes: 42220
def main():
    n = int(input())
    a = list(map(int, input().split()))
      
    b = [0] * (10**6)
    for aa in a:
        b[aa - 1] += 1 
        b[aa + 0] += 1 
        b[aa + 1] += 1 
        
    print(max(b))
        
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
// https://atcoder.jp/contests/abc168/tasks/abc168_d
using Graph = vector<vector<int>>;

int main()
{
	int n, m;
	cin >> n >> m;
	
	Graph G(m+1);
	for(int i=0; i<m; i++)
	{
		int a, b;
		cin >> a >> b;
		
		G[a-1].push_back(b-1);
		G[b-1].push_back(a-1);
	}
	
	// BFS のためのデータ構造
    vector<int> dist(n, -1); // 全頂点を「未訪問」に初期化
    queue<int> que;
    
    vector<int> ans(n, -1);

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[0] = 0;
    que.push(0); // 0 を橙色頂点にする

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            ans[nv] = v;
            que.push(nv);
        }
    }

    // 結果出力 (各頂点の頂点 0 からの距離を見る)
    //for (int v = 0; v < n; ++v) cout << v << ": " << dist[v] << endl;
	
	for (int i = 1; i < ans.size(); i++)
	{
		if(ans[i] == -1)
		{
			cout << "No" << endl;
			return 0;
		}
	}
	
	cout << "Yes" << endl;
	for (int v = 1; v < n; ++v) 
	{
		cout << ans[v]+1 << endl;
	}
	
	return 0;
}


Measured memory_bytes: 12996
#include<bits/stdc++.h>
using namespace std;
long long a=0;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    //cout.setf(ios_base::fixed,ios_base::floatfield);
    int n,m,z=0;
    cin>>n;
    bool a[101]={false};
    for(int i=0;i<n;i++){
        cin>>m;
        a[m]=true;
    }
    for(int i=0;i<101;i++){
        if(a[i]==true) z++;
    }
    cout<<z<<'\n';
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF LLONG_MAX/5
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
int mypow(int a,int b,int c){
	if(b==0)return 1;
	if(b%2)return mypow(a,b-1,c)*a%c;
	int z=mypow(a,b/2,c);
	return z*z%c;
}
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
string s[50];
int x[50];
signed main(){
	int n,ans=0;
	string t;
	cin>>n;
	f(i,n)cin>>s[i]>>x[i];
	cin>>t;
	bool b=false;
	f(i,n){
		if(b)ans+=x[i];
		if(s[i]==t)b=true;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define P pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
void out(vector<string> a,int n){
    rep(j,n){
        cout << a[j];
        if(j!=n-1) cout << " ";
    }
    cout << endl;
}

int value(string s){
    return s[1]-'0';
}

char mark(string s){
    return s[0];
}

vector<string> selectionSort(vector<string> a,int n){
    int cnt = 0;
    rep(i,n){
        int minj = i;
        for(int j=i;j<n;j++){
            if(value(a[j])<value(a[minj])) minj = j;
        }
        swap(a[i],a[minj]);
        if(i!=minj) cnt++;
    }
    //out(a,n);
    //cout << cnt << endl;
    return a;
}
vector<string> bubbleSort(vector<string> a,int n){
    int flag = 1,cnt = 0;
    while(flag){
        flag = 0;
        for(int i=n-1;i>=1;i--){
            if(value(a[i])<value(a[i-1])){
                swap(a[i],a[i-1]);
                cnt++;
                flag = 1;
            }
        }
    }
    //out(a,n);
    //cout << cnt << endl;
    return a;
}

void isStable(vector<string> a,vector<string> b){
    int n = a.size();
    bool ok = true;
    vector<string> c(37),d(37);
    for(int i=1;i<=36;i++){
        rep(j,n){
            if(value(a[j])==i) c[i] += mark(a[j]);
            if(value(b[j])==i) d[i] += mark(b[j]);
        }
    }
    for(int i=1;i<=36;i++){
        if(c[i]!=d[i]) ok = false;
    }
    cout <<(ok ? "Stable" : "Not stable") << endl;
}


int main(){
    int n;
    cin >> n;
    vector<string> a(n),b(n),c(n);
    rep(i,n) cin >> a[i];
    b = bubbleSort(a,n);
    c = selectionSort(a,n);
    out(b,n);
    isStable(a,b);
    out(c,n);
    isStable(a,c);
    return 0;
}


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

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

using lint = long long;

void solve() {
    int n;
    std::cin >> n;

    auto cnt = vec(10, vec(10, 0LL));
    for (int x = 1; x <= n; ++x) {
        int l = x % 10;
        int r = x;
        while (r >= 10) r /= 10;
        ++cnt[l][r];
    }

    lint ans = 0;
    for (int l = 1; l <= 9; ++l) {
        for (int r = 1; r <= 9; ++r) {
            ans += cnt[l][r] * cnt[r][l];
        }
    }

    std::cout << ans << std::endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner

import scala.collection.mutable


object Main {

  case class ResidueRing(private val input: Long) {
    val representative: Long = ((input % ResidueRing.mod) + ResidueRing.mod) % ResidueRing.mod

    def +(that: ResidueRing): ResidueRing = ResidueRing(this.representative + that.representative)

    def -(that: ResidueRing): ResidueRing = ResidueRing(this.representative - that.representative)

    def *(that: ResidueRing): ResidueRing = ResidueRing(this.representative * that.representative)

    def unary_- : ResidueRing = ResidueRing(-this.representative)

  }

  object ResidueRing {
    val mod: Long = (1e9 + 7).toLong
    val _0: ResidueRing = ResidueRing(0)
    val _1: ResidueRing = ResidueRing(1)
  }


  def read() = {
    val sc = new Scanner(System.in)
    val n = sc.nextInt()
    n
  }


  def solve(n: Int): Long = {
    // 過去3文字分記憶しておけばいい
    val alphabets = "ATGC"
    val stateList: IndexedSeq[String] =
      for (c1 <- alphabets;
           c2 <- alphabets;
           c3 <- alphabets) yield IndexedSeq(c1, c2, c3).mkString


    def transition(state: String, alphabet: Char): Option[String] = {
      /*
      (state(0), state(1), state(2), alphabet) match {
        case (_, 'A', 'G', 'C')
             | (_, 'G', 'A', 'C')
             | (_, 'A', 'C', 'G')
             | ('A', _, 'G', 'C')
             | ('A', 'G', _, 'C') => None
        case _ => Some(IndexedSeq(state(1), state(2), alphabet).mkString)
      }
      */
      if ((state + alphabet).matches(""".AGC|.GAC|.ACG|A.GC|AG.C""")) None
      else Some(state.tail + alphabet)
    }

    val mapAll0: mutable.Map[String, ResidueRing] = mutable.Map.empty
    for (state <- stateList) {
      mapAll0.+=((state, ResidueRing._0))
    }
    val dp: Array[mutable.Map[String, ResidueRing]] = Array.fill(n + 1)(mapAll0.clone)

    dp(0)("TTT") += ResidueRing._1
    for (i <- 0 until n) {
      for (state <- stateList) {
        for (alphabet <- alphabets) {
          val next = transition(state, alphabet)
          next match {
            case Some(nextState) => dp(i + 1)(nextState) += dp(i)(state)
            case None =>
          }

        }
      }
    }
    val result = dp.last.values.foldLeft(ResidueRing._0)(_ + _)
    result.representative
  }


  def main(args: Array[String]): Unit = {
    val n = read()
    println(solve(n))
  }
}

Measured memory_bytes: 56716