akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

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

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

  // ll n, w;
  // cin >> n >> w;
  // vector<ll> x(n), v(n);
  // for (int i = 0; i < n; ++i) {
  //   cin >> x[i] >> v[i];
  // }
  // vector<vector<ll>> dp(n + 1, vector<ll>(w + 1));
  // for (int i = 1; i <= n; ++i) {
  //   for (int j = 0; j <= w; ++j) {
  //     dp[i][j] = dp[i - 1][j];
  //     if (x[i - 1] <= j) {
  //       dp[i][j] = max(dp[i][j], dp[i - 1][j - x[i - 1]] + v[i - 1]);
  //     }
  //   }
  // }
  // cout << dp[n][w];

  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  vector<int> dp(k + 1);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (a[i] <= k) {
      dp[a[i]] = 1;
    }
  }

  for (int i = 1; i <= k; ++i) {
    for (int j = 0; j < n; ++j) {
      if (dp[i]) break;
      if (a[j] > i) continue;
      dp[i] = !dp[i - a[j]];
    }
    // cerr << dp[i] << '\n';
  }
  cout << (dp[k] ? "First" : "Second");
}


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

int h, w, n;

void check(vector<int> &boundary) {
    if (boundary[0] < 0) boundary[0]++;
    if (boundary[1] >= h) boundary[1]--;
    if (boundary[2] >= w) boundary[2]--;
    if (boundary[3] < 0) boundary[3]++;
}

int main(){
    cin >> h >> w >> n;
    int sr, sc;
    cin >> sr >> sc;
    sr--;
    sc--;
    string s, t;
    cin >> s >> t;
    vector<char> s_direction = {'U', 'D', 'R', 'L'};
    vector<char> t_direction = {'D', 'U', 'L', 'R'};
    vector<int> boundary(4, 0);
    boundary[1] = h - 1;
    boundary[2] = w - 1;
    vector<int> ds = {1, - 1, - 1, 1};
    vector<int> dt = {- 1, 1, 1, - 1};
    for (int i = 0; i < 4; i++){
        if (s[n - 1] == s_direction[i]) {
            boundary[i] += ds[i];
            check(boundary);
        }
    }

    for (int i = n - 2; i >= 0; i--){
        for (int j = 0; j < 4; j++) {
            if (t[i] == t_direction[j]) {
                boundary[j] += dt[j];
                check(boundary);
            }
        }
        for (int j = 0; j < 4; j++) {
            if (s[i] == s_direction[j]) {
                boundary[j] += ds[j];
                check(boundary);
            }
        }
        if (boundary[0] >= h || boundary[1] < 0 || boundary[2] < 0 || boundary[3] >= w) {
            cout << "NO" << endl;
            exit(0);
        }
    }
    if (boundary[0] <= sr && sr <= boundary[1] && boundary[3] <= sc && sc <= boundary[2]) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
const ll MOD = 1e9+7; ll LLINF = 1LL << 60; int INF = INT_MAX;

//

int main(){
    ll a,b; char o; cin>>a>>o>>b;
    if(o=='+') cout<<a+b<<endl;
    else cout<<a-b<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <utility>
#include <vector>
#include <map>
#include <unordered_map>
#include <cstdlib>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
using ll = long long;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(void)
{
    vector<int> a(6);
    int i, c1=0, c2=0, c3=0, c4=0;

    for(i=0; i<6; i++){
        cin >> a.at(i);

        switch(a.at(i)){
            case 1:
                c1++; break;
            case 2:
                c2++; break;
            case 3:
                c3++; break;
            case 4:
                c4++; break;
        }
    }

    if(c1==3 || c2==3 || c3==3 || c4==3) cout << "NO" << endl;
    else cout << "YES" << endl;

    return 0;
}

Measured memory_bytes: 256
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
    input! {
        n: usize,
        mut a: [i64; n],
        mut b: [i64; n],
    }
    let mut g_n = vec![];
    let mut g_p = vec![];
    for i in 0..n {
        let acc = a[i] - b[i];
        if acc < 0 {
            g_n.push(acc);
        } else {
            g_p.push(acc);
        }
    }

    if g_n.iter().sum::<i64>() + g_p.iter().sum::<i64>() < 0 {
        return println!("-1");
    }

    g_n.sort();
    g_n.reverse();

    g_p.sort();
    g_p.reverse();

    let mut cnt = g_n.len();
    let mut cur = 0;
    let mut used = vec![false; n];
    while let Some(v) = g_n.pop() {
        let mut v_ = v.clone();
        while v_ < 0 && cur < n {
            if v_.abs() <= g_p[cur] {
                if used[cur] == false {
                    cnt += 1;
                    used[cur] = true
                }
                g_p[cur] += v_;
                v_ = 0;
            } else {
                v_ += g_p[cur];
                if used[cur] == false {
                    cnt += 1;
                    used[cur] = true;
                }
                cur += 1;
            }
        }
    }

    println!("{}", cnt);
}


Measured memory_bytes: 6396
from queue import Queue
h,w = map(int, input().split(' '))
s = [list(input()) for _ in range(h)]
num_w = 0
for i in range(h):
    num_w += s[i].count("#")
for i in range(h):
    s[i] = ["#"]+s[i]+["#"]
s.insert(0,["#" for i in range(w+2)])
s.append(["#" for i in range(w+2)])
q = Queue()
cnt = 0
q.put([1,1,0])
s[1][1]="#"
Z = -1
while (not q.empty()):
    x,y,cnt = q.get()
    if (x,y) == (h,w):
        Z = cnt
        break
    for (i,j) in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if s[i][j] != "#":
            s[i][j] = "#"
            q.put([i,j,cnt+1])
if Z == -1:
    print(-1)
else:
    print(h*w-Z-1-num_w)

Measured memory_bytes: 3952
//Referred Professors code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int total = 0;
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            A[i] = Integer.parseInt(st.nextToken());
            total += A[i];
        }
        int count = 0;
        for(int i=0;i<N;i++){
            if (A[i] >= (total * 0.25/ M)){
                count++;
            }
        }
        System.out.println(count>=M?"Yes":"No");
        
    }
}

Measured memory_bytes: 22356
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <numeric>
#include <stack>
#include <cstdlib>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define rep(i, a, N) for(int i = a; i < N; i++)
#define rrep(i, a, N) for(int i = a; i >= N; i--)

const int inf = 1000000000;

//#define DEBUG

int main() {
    string s;
    cin >> s;
    rep(i, 0, s.length()) cout << "x";
    cout << endl;
}

Measured memory_bytes: 888
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct job {
  int defer;
  int value;
};

bool cmp_by_value(const job &a, const job &b) {
  return a.value < b.value || (a.value == b.value && a.defer > b.defer);
}

int main() {
  int n, m; scanf("%d%d", &n, &m);

  vector<job> jobs;

  for (int i = 0; i < n; i++) {
    int d, v;
    scanf("%d%d", &d, &v);
    job tmp;
    tmp.defer = d;
    tmp.value = v;
    jobs.push_back(tmp);
  }

  sort(jobs.begin(), jobs.end(), [](job &a, job &b) {return a.defer < b.defer; } );
  priority_queue<job, vector<job>, decltype(&cmp_by_value)> q(&cmp_by_value);

  int ptr = 0;
  int ans = 0;

  for (int day = 0; day <= m; day++) {
    if (q.size()) {
      ans += q.top().value;
      q.pop();
    }
    while (ptr < n && jobs[ptr].defer == day + 1) {
      q.push(jobs[ptr]);
      ptr++;
    }
  }

  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a, b, c;
  cin >> a;
  int x = a.size();
  for(int i=0; i<x; i++) {
    a.pop_back();
    b = a.substr(0, a.size()/2);
    c = a.substr(a.size()/2);
      if(b==c) {
        cout << a.size() << endl;
        break;
      }
  }
  return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <stdio.h>
#include <cmath>

using namespace std;

int main ()
{
  int N;
  cin >> N;
  int n[100001] = {0};
  for (int i = 0; i < N; i++) {
    int in;
    cin >> in;
    if ((N % 2) == 0 && (in % 2) == 0) {
      printf("0\n");
      return 0;
    } else if ((N % 2) == 1 && (in % 2) == 1) {
      printf("0\n");
      return 0;
    }
    n[in]++;
    if (in == 0 && n[0] == 2) {
      printf("0\n");
      return 0;
    }
    if (n[in] == 3) {
      printf("0\n");
      return 0;
    }
  }

  long ret = 1;
  for(int i = 0; i < (N / 2); i++) {
    ret = ret * 2;
    if (ret > pow(10, 9) + 7) {
      ret = ret - (pow(10, 9) + 7);
    }
  }
  printf("%ld\n", ret);

  return 0;
}



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

int main(){
  string a,b;
  cin >> a;
  cin >> b;
  int i,cnt=0;
  
  for(i=0;i<a.length();i++){
    if(a.at(i)!=b.at(i)){
      cnt++;
    }
  }
  
  cout << cnt << endl;
}

Measured memory_bytes: 3900
## coding: UTF-8
#累積和
N = int(input())
U = list(map(int,input().split()))
D = list(map(int,input().split()))

U = U[::-1]
D = D[::-1]

up = 0
down = 0
upper = [0]
downer = []
for i in range(N):
    up += U[i]
    down += D[i]
    upper.append(up)
    downer.append(down)
upper = upper[::-1]
downer = downer[::-1]
#print(upper)
#print(downer)

ans = 0
for i in range(N):
    ret = upper[0] - upper[i+1] + downer[i]
    ans = max(ans, ret)
print(ans)

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

int main() {
  int h, w, n;
  cin >> h >> w >> n;
  
  int larger = max(h, w);
  int shorer = min(h, w);
  
  int min_num = ceil(double(n) / double(larger));
  
  cout << min_num;
  
  return 0;
}


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

int main() {
 int64_t H,W;
  cin >> H >> W;
  int64_t seki;
  seki= H*W;
    if(H==1 || W==1){
      cout << 1 << endl;
  }  
   else if(seki%2==0){
      cout << seki/2 << endl;
  }
  else if(seki%2==1){
      cout << (seki/2)+1 << endl;
  }  
   
}



Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<string>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	int n; cin >> n;
	int ans = 1;
	int cnt; cin >> cnt;
	for (int i = 1; i < n; i++) {
		int x; cin >> x;
		if (cnt >= x) {
			ans += 1;
		}
		cnt = min(cnt, x);
	}
	cout << ans << '\n';


}


Measured memory_bytes: 256
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int N;
	cin >> N;
	vector<bool> prime(N+1,true);
	prime[0] = false;
	prime[1] = false;
	LL ans = 1;
	LL res = 0;
	for(int i=2;i<=N;++i){
		if( prime[i] ){
			for(int j=i+i;j<=N;j+=i){
				prime[j] = false;
			}
		}else{//素数じゃない
			continue;
		}
		int temp = N;
		LL mul = i;
		LL res = 0;//iの個数
		while(mul <= temp){
			res += temp/mul;
			mul *= i;
		}
		ans *= (res+1);
		ans %= MOD;
	}
	cout << ans << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	
	
	solve();
}
#pragma endregion //main()


Measured memory_bytes: 256
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

c = Counter(A)
ans = 0
even = 0
for v in c.values():
    if v % 2 == 0:
        even += 1
    else:
        ans += 1

if even % 2 == 0:
    ans += even
else:
    ans += even-1


print(ans)

Measured memory_bytes: 18648
n = int(input())
a = list(map(int, input().split()))
sunu = sum(a)
arai = 0
ans = 2*10**9
for i in range(n-1):
  sunu -= a[i]
  arai +=  a[i]
  ans = min(ans,abs(sunu-arai))
  
print(ans)
  
  

Measured memory_bytes: 24932
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
typedef pair<int,int> PI;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
 
typedef struct{
  short x,y;
  int cost;
  short ch;
}mouse;
 
 
mouse t;
short cx,cy,nx,ny,ch,nch,h,w,n;
int cost;
 
main(){
  scanf("%d%d%d ",&h,&w,&n);
  short maxch[h][w];
  char ku[h][w+1];
  
  rep(i,h)fread(ku[i],1,w+1,stdin);
 
 
  rep(i,h)rep(j,w){
    if(ku[i][j]=='S')cx=i,cy=j;
    maxch[i][j]=-1;
  }
 
  queue<mouse> Q;
 
  Q.push((mouse){cx,cy,0,0});
  maxch[cx][cy]=0;
 
  while(!Q.empty()){
    //cout<<Q.size()<<endl;
    t=Q.front();Q.pop();
    cx=t.x,cy=t.y,cost=t.cost;
    ch=t.ch;
 
    rep(i,4){
      nx=cx+dx[i],ny=cy+dy[i];
      if(nx<0 || nx>=h || ny<0 || ny>=w)continue;
      if(ku[nx][ny]=='X')continue;
      nch=ch;
      if(ku[nx][ny]<='9' && ku[nx][ny]>='1' && ku[nx][ny]-'0'==t.ch+1){
        nch=ch+1;
      }
 
      if(maxch[nx][ny]>=nch)continue;
      if(nch==n){
        printf("%d\n",cost+1);
        return 0;
      }
      maxch[nx][ny]=nch;
      Q.push((mouse){nx,ny,cost+1,nch});
    }
  }
}

Measured memory_bytes: 0
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <numeric>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<((x))<<endl
#define fi first
#define se second

#define INF 2147483600
#define long long long

bool solve(int n){
  if(n%2==1) return false;
  int c=0;
  rep(i,n){
    string s;
    cin>>s;
    if(s=="A") c++;
    else {
      if(c==0) return false;
      c--;
    }
  }
  if(c==0) return true;
  else return false;
}

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

  if(solve(n)) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;

  return 0;
}

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()

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

const long long INF = 1LL << 60;

int main()
{
    int N, tmp;
    cin >> N;

    tmp = N;

    int f = 0;
    while (N > 0) {
        f += N % 10;
        N /= 10;
    }

    if (tmp % f == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int N, flag=0;
  cin >> N;
  for(int i=1; i<=9; i++){
    for(int j=1; j<=9; j++){
      if(i*j == N) flag=1;
    }
  }
  if(flag == 0) cout << "No" << endl;
  else cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
ll n,m,q;
ll x[15];
ll a[60],b[60],c[60],d[60];
ll ans=0;
void dfs(ll i0,ll j0){
    x[i0]=j0;
    if(i0==n-1){
        ll tmp=0;
        rep(0,i,q)if(x[b[i]-1]-x[a[i]-1]==c[i])tmp+=d[i];
        ans=max(ans,tmp);
    }else{
       rep(j0,j,m)dfs(i0+1,j); 
    }
}
int main(void){
    cin>>n>>m>>q;
    rep(0,i,q)cin>>a[i]>>b[i]>>c[i]>>d[i];
    rep(0,i,m)dfs(0,i);
    cout<<ans;
}


Measured memory_bytes: 3596
import itertools

# -*- coding: utf-8 -*-
# 整数の入力
H, W, K = map(int, input().split())
# 文字列の入力
masu_list = []
for i in range(H):
    str = input()
    masu_list.append(list(str))
ans = 0

for H_bit in range(1 << H):
    for W_bit in range(1 << W):
        break_i = 0
        cnt = 0
        for i in range(H):
            if break_i == 1:
                break
            for j in range(W):
                if (H_bit >> i) & 1 and (W_bit >> j) & 1:
                    if masu_list[i][j] == "#":
                        cnt += 1
                        if cnt > K:
                            break_i = 1
                            break
        if cnt == K:
            ans += 1
print(ans)


Measured memory_bytes: 9192
#include <iostream>

using namespace std;

int main()
{
    int a;
    string str1, str2;

    cin >> a;
    cin >> str1 >> str2;

    string strsum = "";

    for (int i = 0; i < a ; i++){
        strsum = strsum + str1[i] + str2[i];
    }
    
    cout << strsum << endl;

    return 0;
}


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

using namespace std;

const int mod = 1e9 + 7;
int ans;
int dp[10002][102][2];
char s[10002];
int d;

int main()
{
  cin >> (s + 1);
  cin >> d;
  int n = strlen(s + 1);
  reverse(s + 1,s + n + 1);
  dp[0][0][1] = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < d; j++)
      for (int leq = 1; leq >= 0; leq--)
        for (int cif = 0; cif < 10; cif++) {
          int nextleq = (cif < s[i + 1] - '0' || (cif == s[i + 1] - '0' && leq));
          dp[i + 1][(j + cif) % d][nextleq] += dp[i][j][leq];
          dp[i + 1][(j + cif) % d][nextleq] %= mod;
        }
  cout << (dp[n][0][1] - 1 + mod) % mod;
  return 0;
}


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

using namespace std;

#define sz(vec) ( (int)(vec).size() )
using LL = long long;

int n;
pair<LL, int> ans;
vector<int> d;
vector<LL> c;

pair<int, int> val(int a, int b) {
    pair<int, int> ret{};
    a *= 10; a += b;
    while (a >= 10) {
        ++ret.first;
        a = a / 10 + a % 10;
    }
    ret.second = a;
    return ret;
}

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

//    freopen("input", "r", stdin);

    cin >> n;

    d.assign(n, 0);
    c.assign(n, 0);
    for (int i = 0; i < n; ++i) cin >> d[i] >> c[i];

    ans = make_pair(0, d[0]); --c[0];
    if (!c[0]) {
        d.erase(d.begin() );
        c.erase(c.begin() );
    }

    for (int i = 0; i < sz(d); ++i) {
//        cerr << d[i] << ' ' << c[i] << "=====\n";
        vector<bool> exist(10, false);
        vector<pair<int, int> > tmp;
        int pos = 0;
        tmp.emplace_back(0, ans.second); exist[ tmp.back().second ] = true;
        while (1) {
            auto ret = val(tmp.back().second, d[i]);
            tmp.back().first = ret.first;
            if (exist[ret.second]) {
                for (; pos < sz(tmp); ++pos) if (tmp[pos].second == ret.second) break ;
                break ;
            }
            tmp.emplace_back(0, ret.second); exist[tmp.back().second] = true;
        }

//        for (auto _ : tmp) cerr << _.first << ' ' << _.second << '\n';
//        cerr << tmp[pos].second << '\n';

        int tmp2 = (int)min(c[i], (LL)pos);
        for (int j = 0; j < tmp2; ++j) ans.first += tmp[j].first;
        ans.second = tmp[tmp2].second;

        c[i] -= tmp2;

        int rem = 0;
        for (int j = pos; j < sz(tmp); ++j) rem += tmp[j].first;
        ans.first += (LL)(c[i] / (sz(tmp) - pos) ) * rem;
        rem = (int)(c[i] % (sz(tmp) - pos) );
        for (int j = 0; j < rem; ++j) ans.first += tmp[pos + j].first;
        ans.second = tmp[pos + rem].second;
//        cerr << ans.first << ' ' << ans.second << '\n';
    }

    cout << ans.first;

    return 0;
}


Measured memory_bytes: 2560
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
#define answer(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

// 二分累乗法
Int modpow(Int a, Int n, Int mod) {
    Int ret = 1;
    while (n > 0) {
        if (n & 1) {
            ret = ret * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }

    return ret;
}

vector<Int> factorials(0), invs(0);
bool is_ncr_table = false;
void calc_ncr_table(Int n, Int mod) {
    is_ncr_table = true;

    // 1! ~ n! の計算
    Int f = 1;
    factorials.push_back(f);
    for (Int i = 1; i < n + 1; i++) {
        f *= i;
        f %= mod;
        factorials.push_back(f);
    }
    // n!^-1 の計算
    Int inv = modpow(factorials[n], mod - 2, mod);
    // (n-1)!^-1 ~ 1!^-1 の計算
    invs.assign(n, 1);
    invs[n] = inv;
    for (Int i = n; i >= 1; i--) {
        inv *= i;
        inv %= mod;
        invs[i - 1] = inv;
    }
}

Int factorial(Int n, Int mod = 1) {
    Int ret = 1;
    if (mod == 1) {
        for (Int i = 1; i < n + 1; i++) {
            ret *= i;
        }

        return ret;
    } else {
        for (Int i = 1; i < n + 1; i++) {
            ret *= i;
            ret %= mod;
        }

        return ret;
    }
}

Int ncr(Int n, Int r, Int mod, bool use_table = false) {
    if (use_table) {
        // modが素数の場合のみ
        if (!is_ncr_table) {
            calc_ncr_table(n, mod);
        }
        return factorials[n] * invs[r] * invs[n - r] % mod;
    } else {
        Int x = 1;
        for (Int i = n - r + 1; i < n + 1; i++) {
            x *= i;
            x %= MOD;
        }
        return x * modpow(factorial(r, mod), mod - 2, mod) % mod;
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> p(n), q(n), fac;
    set<int> nu;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> q[i];
    }

    int pn = 0, qn = 0;
    fac.push_back(1);
    for (int i = 1; i <= n; i++) {
        fac.push_back(fac[i - 1] * i);
        nu.insert(i);
    }
    reverse(fac.begin(), fac.end());

    set<int> pa(nu), qa(nu);
    for (int i = 0; i < n; i++) {
        auto itr = pa.find(p[i]);
        pn += (int)distance(pa.begin(), itr) * fac[i + 1];
        pa.erase(itr);
    }
    for (int i = 0; i < n; i++) {
        auto itr = qa.find(q[i]);
        qn += (int)distance(qa.begin(), itr) * fac[i + 1];
        qa.erase(itr);
    }

    cout << abs(qn - pn) << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	class P {
		double x;
		double y;
		double theta;

		P(double x, double y, double theta) {
			this.x = x;
			this.y = y;
			this.theta = theta;
		}

		void goForward(double length) {
			// System.out.println ("gf"+length);

			double nx = Math.cos(theta) * length;
			double ny = Math.sin(theta) * length;
			x += nx;
			y += ny;
		}

	}

	void run() {
		for (;;) {
			int n = sc.nextInt();
			int d = sc.nextInt();

			if ((n | d) == 0) {
				break;
			}
			P p = new P(0, 0, Math.PI / 2);

			for (int i = 0; i < n; i++) {
				double l = sc.nextInt();
				double r = sc.nextInt();
				double t = sc.nextInt();
				if (l == r) {
					p.goForward(l * t / 180.0 * Math.PI);
				} else if (l == -r) {
					l *= t / 180.0 * Math.PI;
					p.theta -= l / d;
				} else {
					double nx = 0;
					double ny = 0;
					l *= t / 180.0 * Math.PI;
					r *= t / 180.0 * Math.PI;
					if (l == 0) {
						nx = p.x + d * Math.cos(p.theta + Math.PI / 2);
						ny = p.y + d * Math.sin(p.theta + Math.PI / 2);
					} else {
						double lx = p.x + d * Math.cos(p.theta + Math.PI / 2);
						double ly = p.y + d * Math.sin(p.theta + Math.PI / 2);
						nx = lx + 2 * d * Math.cos(p.theta - Math.PI / 2)
								* ((double) l / (l - r));
						ny = ly + 2 * d * Math.sin(p.theta - Math.PI / 2)
								* ((double) l / (l - r));
					}
					double xx = p.x - nx;
					double yy = p.y - ny;

					double rr = Math.sqrt(xx * xx + yy * yy);

					double rot = 0;

					rot += Math.atan2(yy, xx);
					if (Math.abs(l) > Math.abs(r)) {
						rot += -(l + r) / (2 * rr);
						p.theta = rot - Math.PI / 2;

					} else {
						rot += (l + r) / (2 * rr);
						p.theta = rot + Math.PI / 2;

					}
//					System.out.println(nx + " " + ny + " r" + rr);

					p.x = nx + rr * (Math.cos(rot));
					p.y = ny + rr * (Math.sin(rot));
				}
//				System.out.println(p.x + " " + p.y + " " + p.theta);
			}
			int px10000 =(int) (p.x*10000+0.5) ;
			int py10000 =(int) (p.y*10000+0.5);
			System.out.println(px10000/10000.0);
			System.out.println(py10000/10000.0);
		}
	}

	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}
}

Measured memory_bytes: 12000
def p(x):
  print('{0:.6f}'.format(x))
from math import sqrt,sin,cos,pi

a,b,C = map(float,input().split())
theta = pi*C/180
h,c = 0.0,0.0

if theta<=pi/2:
  h = b*sin(theta)
  x = sqrt(b*b-h*h)
  c = sqrt(h**2+(a-x)**2)

else:
  phi = theta-pi/2
  h = b*cos(phi)
  d = b*sin(phi)
  e = a*h/(a+d)
  f = sqrt(d**2+(h-e)**2)
  g = sqrt(a**2+e**2)
  c = f+g

S = a*h/2
L = a+b+c
p(S)
p(L)
p(h)


Measured memory_bytes: 5676
#include <stdio.h>
#define N 100005

typedef struct{
  char p[100];
  int t;
}Pro;

void enqueue(Pro);
Pro dequeue(void);
int min(int, int);

Pro Q[N];
int head = 0, tail = 0, n = 0;

int main(){
  int elasp = 0, q = 0, c = 0;
  int i = 0;
  Pro u;

  /*Scan*/
  scanf("%d%d",&n,&q);

  for(i = 1; i <= n; i++){
    scanf("%s%d",Q[i].p,&(Q[i].t));
  }

  head = 1;
  tail = n+1;
  /*Queue*/
  while(head != tail){
    u = dequeue();
    c = min(q, u.t);
    u.t  = u.t - c;
    elasp = elasp + c;
    if(u.t > 0)enqueue(u);
    else printf("%s %d\n",u.p,elasp);
  }

  return 0;
}

void enqueue(Pro x){
  Q[tail] = x;
  tail = (tail + 1) % N;
}

Pro dequeue(){
  Pro x = Q[head];
  head = (head + 1) % N;
  return x;
}

int min(int a, int b){
  if(a < b)return a;
  else return b;
}



Measured memory_bytes: 11852
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

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;
}


signed main(void) {
    int n;
    cin >> n;
    vi h(n);
    rep(i,n)cin >> h[i];
    sort(all(h));
    int ans = 1;
    int t = 0;
    loop(i,1,126){
        while(t < n && h[t] < i)t++;
        int num = n - t;//iマス目に到達できる人数
        ans += min(num, i*4);//iマス目は高々 i*4 マスしかない
    }
    rep(i,n)if(h[i] > 125) ans += h[i] - 125;
    cout << ans << endl;
}



Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,M,C;
  cin>>N>>M>>C;
  vector<int> B(M);
  for(int &i:B)
    cin>>i;
  int l=0;
  while(N--){
    int k=C;
    for(int i=0;i<M;i++){
      int A;
      cin>>A;
      k+=A*B[i];
    }
    if(k>0)
      l++;
  }
  cout<<l<<endl;
}

Measured memory_bytes: 3544
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
#include <map>
#include <queue>
#include <list>
#include <functional>
#include <numeric>
#include <stack>
#include <tuple>
#include <fstream>
using namespace std;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
const int INF = 100000000;
const long long LINF = 1000000000000000000;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-6;
const double pi = 3.14159265359;
using pii = std::pair<int, int>;
using ll = long long;
using pLL = std::pair<ll, ll>;
#define SORT(v) std::sort(v.begin(), v.end())
#define RSORT(v) std::sort(v.rbegin(), v.rend())
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    cout <<  n* n * 3 << endl;
    return 0;
}

Measured memory_bytes: 256
fn main() {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    println!("{}", solve(&input));
}

fn solve(input: &str) -> i64 {
    let mut iter = input.split_whitespace().map(|w| w.parse().unwrap());
    let n: i64 = iter.next().unwrap();
    let k: i64 = iter.next().unwrap();
    if n == 0 {
        1
    } else {
        let mut n = n;
        let mut cnt = 0;
        while n != 0 {
            cnt += 1;
            n /= k;
        }
        cnt
    }
}

Measured memory_bytes: 4352
# 入力　文字列3つ、別々に
SA = input()
SB = input()
SC = input()

next = "a"
a_i = 0
b_i = 0
c_i = 0

while next :
    if next == "a" :
        try :
            next = SA[a_i]
            a_i += 1
        except :
            break
    elif next == "b" :
        try :
            next = SB[b_i]
            b_i += 1
        except :
            break
    else :
        try :
            next = SC[c_i]
            c_i += 1
        except :
            break

print(next.upper())


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
constexpr int INF = 2e9;
int main(){ 
  int a, b;
  cin >> a >> b;
  if (a <= b) cout << "unsafe" << endl;
  else cout << "safe" << endl;
  return 0;
} 

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

int main() {
  int N; cin >> N;
  vector<long long> t(N+1);
  vector<long long> x(N+1);
  vector<long long> y(N+1);
  t[0] = 0, x[0] = 0, y[0] = 0;
  for(int i = 1; i <= N; ++i) {
    cin >> t[i] >> x[i] >> y[i];
  }
  for(int i = 1; i <= N; ++i) {
    int dt = abs(t[i] - t[i-1]);
    int dx = abs(x[i] - x[i-1]);
    int dy = abs(y[i] - y[i-1]);
    if(dt < dx+dy) {
      cout << "No" << endl;
      return 0;
    } else if (dt % 2 != (dx + dy) % 2) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;

  return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
int V, E, R, S[500010], T[500010], D[500010]; 
int C[100010]; 
const int Inf = 10000*100000+100;

int main(){
    cin >> V >> E >> R;
    vector<pair<int, int> > tmp(0);
    vector<vector<pair<int, int> > > edges(V+10);
    for(int i = 0; i < E; i++){
        int s, t, d;
        cin >> s >> t >> d;
        edges[s].push_back(make_pair(t, d));
    }
    auto c = [](pair<int, int> &l, pair<int, int> &r){return l.first > r.first;};
    priority_queue<pair <int,int> , vector<pair<int, int> >, decltype(c)> Q(c);
    Q.push(make_pair(0, R));
    for(int i=0;i<V;i++){
        C[i] = Inf;
    }
    C[R] = 0;
    while(!Q.empty()){
        pair<int,int> t = Q.top();
        Q.pop();
        int s = t.second;
        if(C[s] >= t.first){
            for(auto edge : edges[s]){
                if(C[edge.first] > C[s] + edge.second){
                    C[edge.first] = C[s] + edge.second;
                    Q.push(make_pair(C[edge.first],edge.first));
                }
            }
        }
    }
    for(int i = 0; i < V; i++){
        if(C[i] == Inf){
            cout << "INF" << endl;
        }else{
            cout << C[i] << endl;
        }  
    }
}

Measured memory_bytes: 12948
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>
#include <bitset>
#include <cassert>


// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

const int N = 310;
int a[N];
int sum[N];

ll dp[N][N];

int calc(ll x, ll y){
	int ret = 0, c = 0;
	rep(i, 12){
		if (c) ++ret;
		int xx = x % 10, yy = y % 10;
		x /= 10, y /= 10;
		c = (xx + yy + c) / 10;
		ret += xx*yy;
	}
	return ret;
}

ll rec(int l, int r){
	if (r - l <= 1) return 0;
	ll &res = dp[l][r];
	if (res + 1) return res;

	res = 1e18;
	for (int i = l+1; i < r; ++i){
		res = min(res, rec(l, i) + rec(i, r) + calc(sum[r] - sum[i], sum[i] - sum[l]));
	}
	return res;
}

int main(){
	int n;
	cin >> n;
	rep(i, n) cin >> a[i];
	rep(i, n) sum[i + 1] = sum[i] + a[i];

	MEMSET(dp, -1);
	cout << rec(0, n) << endl;

	return 0;
}

Measured memory_bytes: 1936
#include <bits/stdc++.h>
#include<math.h>
#include<algorithm> 
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 1e18

int main() {
    int n ;
    cin >> n ;
    vector<int> a (n) ;
    vector<int> b (1000005) ;
    rep(i, n){
        cin >> a[i] ;
        b[a[i]] += 1 ;
    }
    sort(a.begin(),a.end()) ;
    int mx = a[n - 1] ;
    vector<int> nums (mx + 1) ;
    rep(i, n){
        int f = a[i] ;
        for(int j = 2*f; j <= mx; j += f){
            if(nums[j] == 0){
                nums[j] += 1 ;
            }
        }
    }
    int ans = 0 ;
    rep(i, n){
        if(nums[a[i]] == 0 && b[a[i]] == 1){
            ans++ ;
        }
    }
    cout << ans << endl ;
}

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

using namespace std;

#define int long long
#define endl "\n"

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

const int N = 1e5 + 5;
int n, a[N], b[N], c[N];

int dp[N][3];

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

	//rwf();

	cin >> n;

	memset(&dp, 0, sizeof(dp));

	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}

	dp[1][0] = a[1], dp[1][1] = b[1], dp[1][2] = c[1];

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

	int ans = max(dp[n][0], max(dp[n][1], dp[n][2]));

	cout << ans;

	return 0;
}

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

int main()
{
    int N, K;
    string S;
    cin >> N >> S >> K;
    for (int i = 0; i < N; i++)
    {
        if (S.at(K - 1) != S.at(i))
        {
            S.at(i) = '*';
        }
    }
    cout << S << endl;
}

Measured memory_bytes: 256
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace ABC117D
{
    public class Program
    {
        void Solve(StreamScanner ss, StreamWriter sw)
        {
            //---------------------------------
            const int MAX = 50;

            var N = ss.Next(int.Parse);
            var K = ss.Next(long.Parse);
            var A = ss.Next(long.Parse, N);

            var pops = new long[MAX];
            foreach (var a in A)
            {
                for (var i = 0; i < MAX; i++)
                {
                    if (((a >> i) & 1) == 1) pops[i]++;
                }
            }

            var memo = new long[MAX];
            for (var i = 0; i < MAX; i++)
            {
                var place = 1L << i;
                memo[i] += Math.Max(N - pops[i], pops[i]) * place;
                if (i > 0) memo[i] += memo[i - 1];
            }

            var ans = 0L;
            var current = 0L;
            var kBase2 = Convert.ToString(K, 2);
            var kBase2Rev = (new string('0', MAX - kBase2.Length) + kBase2).Select(c => c - '0').Reverse().ToArray();

            for (var i = MAX - 1; i >= 0; i--)
            {
                var place = 1L << i;

                if (kBase2Rev[i] == 0)
                {
                    current += pops[i] * place;
                }
                else
                {
                    if (i > 0) ans = Math.Max(ans, current + pops[i] * place + memo[i - 1]);
                    current += (N - pops[i]) * place;
                }
            }

            ans = Math.Max(ans, current);
            sw.WriteLine(ans);
            //---------------------------------
        }

        static void Main()
        {
            var ss = new StreamScanner(new StreamReader(Console.OpenStandardInput()));
            var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            new Program().Solve(ss, sw);
            sw.Flush();
        }
    }

    public class StreamScanner
    {
        static readonly char[] Sep = {' '};
        readonly Queue<string> buffer = new Queue<string>();
        readonly TextReader textReader;

        public StreamScanner(TextReader textReader)
        {
            this.textReader = textReader;
        }

        public T Next<T>(Func<string, T> parser)
        {
            if (buffer.Count != 0) return parser(buffer.Dequeue());
            var nextStrings = textReader.ReadLine().Split(Sep, StringSplitOptions.RemoveEmptyEntries);
            foreach (var nextString in nextStrings) buffer.Enqueue(nextString);
            return Next(parser);
        }

        public T[] Next<T>(Func<string, T> parser, int x)
        {
            var ret = new T[x];
            for (var i = 0; i < x; ++i) ret[i] = Next(parser);
            return ret;
        }

        public T[][] Next<T>(Func<string, T> parser, int x, int y)
        {
            var ret = new T[y][];
            for (var i = 0; i < y; ++i) ret[i] = Next(parser, x);
            return ret;
        }
    }
}

Measured memory_bytes: 31196
import itertools
import math
N, D = map(int, input().split())
cnt = 0
lst = []
for i in range(N):
    lst.append(list(map(int, input().split())))
for x, y in itertools.combinations(lst, 2):
    leng = 0
    for d in range(D):
        leng += (x[d] - y[d])**2
    leng = math.sqrt(leng)       
    if leng == int(leng):
        cnt += 1
print(cnt)

Measured memory_bytes: 3064
module Main where

import Control.Applicative
import Numeric
import Data.List (transpose)


main :: IO ()
main = do
  { [r, c] <- getInts
  ; mat <- loop r
  ; mapM_ putInts (hoge mat)
  }

loop :: Int -> IO [[Int]]
loop 0 = return []
loop r = do
  { xs <- getInts
  ; xss <- loop (r-1)
  ; return (xs : xss)
  }

hoge :: [[Int]] -> [[Int]]
hoge = transpose . map addSum . transpose . map addSum

addSum :: [Int] -> [Int]
addSum xs = xs ++ [sum xs]

--
getInts :: IO [Int]
getInts = map read . words <$> getLine

putInts :: [Int] -> IO ()
putInts = putStrLn . unwords .  map show

getDoubles :: IO [Double]
getDoubles = map read . words <$> getLine

putDoubles :: [Double] -> IO ()
putDoubles = putStrLn . unwords . map showDouble

showDouble :: Double -> String
showDouble d = showFFloat Nothing d ""


Measured memory_bytes: 8340
a,b,h,m = map(int, input().split())
import math
a_x = a * math.cos(math.radians(30*h + 0.5*m))
a_y = a * math.sin(math.radians(30*h + 0.5*m))
b_x = b * math.cos(math.radians(6*m))
b_y = b * math.sin(math.radians(6*m))

ans = math.sqrt(abs(a_x - b_x)**2 + abs(a_y - b_y)**2)
print(ans)


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


struct Job
{
	Job()
	: Job(0,0)
	{}
	
	Job(int a, int b)
	:
	a(a),
	b(b)
	{}
	
	int a, b;
	bool operator <(Job &b)
	{
		return this->b < b.b;
	}
};

using namespace std;

int main()
{
	int n, i, j, a, b;
	cin >> n;
	Job ar[n];
	
	
	for (i = 0; i < n; ++i)
	{
		cin >> a >> b;
		ar[i] = Job(a, b);
	}
	
	sort(ar, ar+n);
	int time = 0;
	for (i = 0; i < n; ++i)
	{
		if (ar[i].a <= (ar[i].b - time))
		{
			time += ar[i].a;
		}
		else
		{
			cout << "No";
			return 0;
		}
	}
	
	cout << "Yes";
	return 0;
	
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

int main(){
  ll n,k;
  ll a[111111],b[111111];
  ll ans=0;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    
    int f=0;
    for(int j=0;j<=30;j++){
	 if((a[i]>>j&1)&&((k>>j&1)==0))f=1;
    }
    if(f)continue;
    ans+=b[i];
  }

  //cout<<ans<<endl;

  for(int i=0;i<=30;i++){
    if((k>>i&1)==0)continue;
    //    dbg(i);
    ll tmp=0;
    ll r=k-(1LL<<i);
    for(int j=0;j<n;j++){
	 int f=0;
	 for(int l=i;l<=30;l++){
	   if((a[j]>>l&1)&&((r>>l&1)==0))f=1;
	 }
	 if(f)continue;
	 tmp+=b[j];
    }
    ans=max(ans,tmp);
    //    dbg(ans);
  }

  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1792
#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 20;

int x[N],y[N],p[N];
int dis[N];
LL ans[N];
int vis[N];

int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&p[i]),ans[i]=1e18;
	ans[0] = 1e18;
	
	for(int i=0;i<(1<<n);i++){
		int num=0;
		for(int j=0;j<n;j++) if((i>>j)&1) vis[++num] = j+1;  //此次建num个road 
		
		for(int j=0;j<(1<<num);j++){
			
			for(int k=1;k<=n;k++) dis[k] = min(abs(x[k]),abs(y[k]));
			
			for(int k=0;k<num;k++){
				if((j>>k)&1){	//在num个road里选x方向建road 
					for(int t=1;t<=n;t++) dis[t] = min(dis[t],abs(x[t]-x[vis[k+1]]));
				}	//维护每个站到新road的最短距离 
				else{
					for(int t=1;t<=n;t++) dis[t] = min(dis[t],abs(y[t]-y[vis[k+1]]));
				} 
			}
			LL s=0;
			for(int k=1;k<=n;k++) s += (LL)dis[k]*p[k];
			ans[num] = min(ans[num],s);
		}
	}
	for(int i=0;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}

Measured memory_bytes: 1732
using System;
using System.Collections.Generic;
using System.Text;

namespace AtCoder
{
  class Program
  {
    static void Main(string[] args)
    {
      long mod = 1000000007;
      int N = int.Parse(Console.ReadLine());
      int c = 0;
      for(int i = 0; i < N; i++)
      {
        string[] ss = Console.ReadLine().Split(' ');
        int i1 = int.Parse(ss[0]);
        int i2 = int.Parse(ss[1]);
        if(i1 == i2)
          c++;
        else
          c = 0;
        if(c == 3)
        {
          Console.WriteLine("Yes");
          return;
        }
      }
      Console.WriteLine("No");
      //int N = int.Parse(Console.ReadLine());

      //long[] ns = new long[2001];
      //for(int i = 3; i <= N; i++)
      //{
      //  long x = 1;
      //  for(int j = 3; j <= i - 3; j++)
      //  {
      //    x += ns[j];
      //    x %= mod;
      //  }
      //  ns[i] = x;
      //}

      Console.ReadLine();
    }
    
  }
}

Measured memory_bytes: 27532
a, b, c, d = list(input())
a = int(a)
b = int(b)
c = int(c)
d = int(d)
if 0 < 10*a + b <= 12 and 0 < c*10 + d <= 12:
    print('AMBIGUOUS')
elif (10*a + b >= 12 or a + b == 0) and 0 < c*10 + d <= 12:
    print('YYMM')
elif 0 < 10*a + b <= 12 and (c*10 + d >= 12 or c + d == 0):
    print('MMYY')
else:
    print('NA')



Measured memory_bytes: 3060