akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <list>
#include <utility>
#include <set>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <random>

using namespace std;

static const double EPS = 1e-9;
template<class T> bool INRANGE(T x, T a, T b) { return a <= x&&x <= b; }
template<class T> void amin(T &a, T v) { if (a > v) a = v; }
template<class T> void amax(T &a, T v) { if (a < v) a = v; }
int ROUND(double x) { return (int)(x + 0.5); }
bool ISINT(double x) { return fabs(ROUND(x) - x) <= EPS; }
bool ISEQUAL(double x, double y) { return fabs(x - y) <= EPS*max(1.0, max(fabs(x), fabs(y))); }
double SQSUM(double x, double y) { return x*x + y*y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
#define NG (-1)
#define BIG ((int)1e9+10)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef unsigned long long ull;
typedef long long ll;

int main()
{
	int N, K, Q;
	cin >> N >> K >> Q;

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

	ll ans = BIGLL;
	for (int i = 0; i < N; ++i)
	{
		// a[i]以上のに着目
		vector <int> tmp;

		vector <int> x;

		for (int k = 0; k < N; ++k)
		{
			if (a[k] >= a[i])
			{
				tmp.push_back(a[k]);
			}
			else
			{
				sort(tmp.begin(), tmp.end());
				const int pickNum = SZ(tmp) - K + 1;
				for (int s = 0; s < pickNum; ++s)
				{
					x.push_back(tmp[s]);
				}
				tmp.clear();
			}
		}

		sort(tmp.begin(), tmp.end());
		const int pickNum = SZ(tmp) - K + 1;
		for (int s = 0; s < pickNum; ++s)
		{
			x.push_back(tmp[s]);
		}
		tmp.clear();

		sort(x.begin(), x.end());

		if (SZ(x)>=Q)
		{
			ll kouho = x[Q - 1] - x[0];
			amin(ans, kouho);
		}
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cmath>
#include <string>
#include <array>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <utility>
#include <iomanip>
#include <numeric>
#include <climits>
#include <algorithm>
#include <cstdint>
using namespace std;

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

    x -= a;
    while (x - b >= 0)
        x -= b;
    cout << x;
}

Measured memory_bytes: 3668
/*In the name of Allah*/
#include<stdio.h>
#include<math.h>
#include<limits.h>
#include<assert.h>
#include<stdbool.h>
#include<stddef.h>
#include<stdint.h>
#include<string.h>
#include<unistd.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
typedef long long ll;
typedef long double ld;

#define s(a) scanf("%lld",&a)
#define p(a) printf("%lld",a)
#define nl printf("\n")
#define space printf(" ")
#define pi acos(-1)

#define FOR1(i,n) for(ll i=1;i<=n;i++)
#define FOR0(i,n) for(ll i=0;i<n;i++)

int main()
{ 
ll n,t,sum=0;
    s(n);
     t=n/500; n%=500;t=t*1000;
    sum+=t; t=n/5; t=t*5;
    sum+=t;
    
    p(sum);
    
    
    nl; 
  



return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int a;
  int b;
  int r;
  cin >> a;
  cin >> b;
  r= a * b;
  if (r % 2 == 0) { cout << "Even" << endl; }
  else { cout << "Odd" << endl;}
}


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

int main() {
  string s;
  int count = 0;
  cin >> s;
  if(s[0] == '1') count++;
  if(s[1] == '1') count++;
  if(s[2] == '1') count++;
  
  cout << count << endl;
}


Measured memory_bytes: 256
n = int(input())
abc  = [[], [], []]

abc = [list(map(int, input().split())) for _ in range(n)] # DB取得方法のみ違う, 分かればどっちでもok
#print(abc)

dp = [[0,0,0] for _ in range(n)]
dp[0] = abc[0]
#print(dp)

for i in range(1, n):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i][j] = max(dp[i][j], dp[i-1][k] + abc[i][j]) # ここのDB指定方法に影響

print(max(dp[-1]))

Measured memory_bytes: 77144
#include<iostream>
#include<string>
#include<cctype>
#include<set>
#include<cstring>
#include<cstdio>

using namespace std;

string detectPalindrome(char *tex, int len, int c){
  int pre = c-1;
  int next = c+1;

  while(true){
    if( pre < 0 || next >= len ){
      ++pre;
      --next;
      break;
    }
    if( tex[pre] != tex[next] ){
      ++pre;
      --next;
      break;
    }
    --pre;
    ++next;
  }
  
  if(tex[pre]==tex[next])
    return string( tex+pre,tex+next+1 );
  return "";
}

int main()
{
  string t;
  while( getline(cin,t) ){
    char tex[2048] ={0,};
    int len = 0;
    set<string> S;

    tex[len]='$';
    ++len;
    for(int i = 0; i < (int)t.length(); ++i){
      if(isalpha(t[i])){
        tex[len] = toupper( t[i] );
        ++len;
        tex[len] = '$';
        ++len;
      }
    }

    // cout << tex << endl;

    for(int i = 0; i < len; ++i){
      string ret = detectPalindrome(tex,len,i);

      if(ret.length()>6){
        //cout <<"PALIN:"<<ret <<endl;

        bool ng = false;

        for(set<string>::iterator it = S.begin(); it != S.end();){
          int c1 = ret.length()/2;
          int c2 = it->length()/2;
          
          while(true){
            if(c1>=(int)ret.length()||c2>=(int)it->length()){
              --c1;
              --c2;
              break;
            }
            if(ret[c1]!=(*it)[c2]){
              break;
            }
            ++c1;
            ++c2;
          }

          //cout << c1 << ' ' << c2 << endl;

          if(ret[c1]==(*it)[c2]){
            //cout << "SAME?:"<< ret << ' ' << *it << endl;
            ng=true;
            if(ret.length()>it->length()){
              S.erase(it);
              S.insert(ret);
              it = S.begin();
            }else{
              break;
            }
          }

          ++it;
        }
        
        if(!ng){
          S.insert(ret);
        }
      }
    }

    for(set<string>::iterator it = S.begin(); it != S.end(); ++it){
      if(it!=S.begin())putchar(' ');
      for(int i = 0; i < (int)it->length(); ++i){
        if(isalpha( (*it)[i] )){
          putchar( (*it)[i] );
        }
      }
      
    }
    putchar('\n');
    
  }
  return 0;
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
using namespace std;
#define N 1111116
#define mod 1000000007

int n,f[N],cnt;

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	int n=read();
	f[1]=n;f[2]=1ll*n*n%mod;cnt=(f[1]+f[2])%mod;
	for (int i=3;i<=n;i++)
		f[i]=(1ll*(n-1)*(n-1)+(n-i+2)+cnt-f[i-2]+mod)%mod,
		cnt=(cnt+f[i])%mod;
	printf("%d\n",f[n]);
	return 0;
}

Measured memory_bytes: 4352
n=int(input())
cnt=[[0]*10 for i in range(10)]
for i in range(1,n+1):
  s=str(i)
  h=int(s[0])
  t=int(s[-1])
  cnt[h][t]+=1
ans=0
for i in range(10):
  for j in range(10):
    ans+=cnt[i][j]*cnt[j][i]
print(ans)


Measured memory_bytes: 3060
from collections import defaultdict
N = int(input())
S = defaultdict(int)
S_item = []
for _ in range(N):
    s = input()
    S[s] += 1
    S_item += [s]
M = int(input())
T = defaultdict(int)
T_item = []
for _ in range(M):
    t = input()
    T[t] += 1
    T_item += [t]
ans = 0
for item in S_item:
    if item not in T_item:
        ans = max(ans, S[item])
    else:
        ans = max(ans, S[item]-T[item])
print(ans)

Measured memory_bytes: 3316
H, W=map(int, input().split())
S=[]
from math import ceil

for h in range(H):
    s=list(input())
    S.append(s)

dp = [[float("INF")]*W for _ in range(H)]
if S[0][0]=="#":
    dp[0][0]=1
else:
    dp[0][0]=0

for h in range(H):
    for w in range(W):
        if w==0 and h==0:
            continue
        if h==0:
            if S[h][w] == S[h][w-1]:
                now=0
            else:
                now=1
            dp[h][w]=min(dp[h][w-1]+now, dp[h][w])
        elif w==0:
            if S[h][w] == S[h-1][w]:
                now=0
            else:
                now=1
            dp[h][w]=min(dp[h-1][w]+now, dp[h][w])
        else:
            if S[h][w]==S[h][w-1]:
                noww = 0
            else:
                noww=1
            if S[h][w]==S[h-1][w]:
                nowh = 0
            else:
                nowh=1
            dp[h][w] = min(dp[h][w], dp[h][w-1]+noww, dp[h-1][w]+nowh)
ans = ceil(dp[-1][-1]/2)
print(ans)

Measured memory_bytes: 74592
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long double PI = acos(-1.0);
// cout << fixed << setprecision(14);
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N >> K;
	int A[N];
	rep(i,N) cin >> A[i];
	sort(A, A+N);
	int ans = 0;
	rep(i,K){
		ans += A[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 3648
fun main() {
    val inLine = readLine()!!.split(" ").map(String::toInt)

    val x = inLine[0]
    val y = inLine[1]

    var k = 0

    var result = "No"
    run loop@{
        while(k <= x){
            var fNum = k * 2 + (x - k) * 4
            if(fNum == y){
                result = "Yes"
                return@loop
            }
            k++
        }
    }

    println(result)
}

Measured memory_bytes: 36348
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    string s,t;
    int i;
    //string ans="No";
    cin>>s>>t;
    vector<int> ss(26,0);
    vector<int> tt(26,0);
    for(i=0;i<s.size();i++){
 ss[((int)s[i])-97]++;
    }
    for(i=0;i<t.size();i++){
        tt[((int)t[i])-97]++;
    }
    sort(ss.begin(),ss.end());
    sort(tt.begin(),tt.end());
if(ss==tt)cout <<"Yes"<<endl;
    else cout <<"No" <<endl;

   // std::cout << (int)'c' << std::endl;
    return 0;//4214888
}

Measured memory_bytes: 776
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[5];
int main()
{
  cin>>a[0]>>a[1]>>a[2];
  sort(a,a+3);
  cout<<a[0]+a[1]<<endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class C
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		Console.WriteLine(new int[n].Select(_ => long.Parse(Console.ReadLine())).Where(IsPrime).Count());
	}

	static bool IsPrime(long n)
	{
		for (long x = 2; x * x <= n; ++x) if (n % x == 0) return false;
		return n > 1;
	}
}



Measured memory_bytes: 16244
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define	REP(i,n) for(int i = 0;	i < (int)(n); i++)
typedef	long long ll;

int main() {
  int N; cin>>N;
  vector<string> s(N);
  REP(i,N) {
    string data; cin>>data;
    sort(data.begin(), data.end());
    s[i] = data;
  }
  sort(s.begin(), s.end());
  ll ans = 0;
  ll cnt = 0;
  for(int i = 1; i < N; i++) {
    if(s[i-1] == s[i]) {
      cnt++;
      ans += cnt;
    } else cnt = 0;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
import java.io.*;
import java.io.IOException;
import java.util.*;

@SuppressWarnings({"rawtypes", "unchecked"})
class Main {
    final static int INF = 1 << 28;
    final static long LNF = 1L << 60;
    final static double EPS = 1e-9;
    final static double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;

    static final long MOD = 1_000_000_007;

    public static void main(String[] args) throws Exception {
        final MyScanner sc = new MyScanner();
        long N;
        N = sc.nextLong();
        long X;
        X = sc.nextLong();
        long Y;
        Y = sc.nextLong();
        solve(N, X, Y);
    }

    static void solve(long N, long X, long Y){
        long[] ans = new long[(int)N-1];
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                ans[Math.min(j-i, Math.abs((int)X-i-1)+1+Math.abs((int)Y-j-1)) - 1]++;
            }
        }
        for (long l: ans) {
            System.out.println(l);
        }
    }


    static class MyScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        MyScanner(FileReader fileReader) {
            br = new BufferedReader(fileReader);
        }
 
        MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String nn() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        String next() {
            return nn();
        }

        String nextLine() {
            String ans = "";
            try {
                ans = br.readLine();
            } catch (IOException ex) {
                ex.printStackTrace();
            }
            return ans;
        }
 
        char nextChar() {
            return nn().charAt(0);
        }
 
        int nextInt() {
            return Integer.parseInt(nn());
        }
 
        long nextLong() {
            return Long.parseLong(nn());
        }
 
        double nextDouble() {
            return Double.parseDouble(nn());
        }
 
        Integer[] niArr0(int n) {
            Integer[] ar = new Integer[n];
            for (int i = 0; i < n; i++) {
                ar[i] = nextInt();
            }
            return ar;
        }
 
        Integer[] niArr1(int n) {
            Integer[] ar = new Integer[n + 1];
            for (int i = 1; i <= n; i++) {
                ar[i] = nextInt();
            }
            return ar;
        }
 
        Long[] nlArr0(int n) {
            Long[] ar = new Long[n];
            for (int i = 0; i < n; i++) {
                ar[i] = nextLong();
            }
            return ar;
        }
 
        Long[] nlArr1(int n) {
            Long[] ar = new Long[n + 1];
            for (int i = 1; i <= n; i++) {
                ar[i] = nextLong();
            }
            return ar;
        }
    }

}


Measured memory_bytes: 24016
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean[] isSosu = new boolean[100010];

		for(int i = 2; i < 100010; i++) {
			int warare = i;
			boolean isSo = true;
			for(int warusu = 2; warusu * warusu <= warare; warusu++) {
				if(warare%warusu==0) {
					isSo = false;
					break;
				}
			}
			isSosu[i]=isSo;
		}
		int st, en;
		int[] ruisekiWA = new int[100000];
		for(int i = 3; i < 100000; i++) {
			ruisekiWA[i] = ruisekiWA[i-1];
			if(i%2==1&&isSosu[i]==true&&isSosu[(i+1)/2]==true) {
				ruisekiWA[i]++;
			}
		}
		for(int i = 0; i < n; i++) {
			st=sc.nextInt();
			en=sc.nextInt();
			System.out.println(ruisekiWA[en]-ruisekiWA[st-1]);
		}
	}
}

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

int main() {
  int x1,y1,x2,y2; cin >>x1>>y1>>x2>>y2;
  int diffx,diffy;
  diffx = (x2-x1);
  diffy = (y2-y1);
    cout <<x2-diffy<<" "<<y2+diffx<<" "<<x1-diffy<<" "<<y1+diffx<<endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <algorithm>
#include <sstream>
#include <list>

using namespace std;

int main()
{
	int N;
	vector<int> H;

	cin >> N;

	int i, j;
	H.resize(N);

	int res = 0;
	bool flg;
	int max = 0;

	for (i = 0; i < N; i++)
	{
		cin >> H[i];
		if (H[i] >= max)
		{
			res++;
			max = H[i];
		}
	}

	printf("%d", res);
	 
	return 0;
}


Measured memory_bytes: 888
// Problem : E - Count Median
// Contest : AtCoder - AtCoder Beginner Contest 169
// URL : https://atcoder.jp/contests/abc169/tasks/abc169_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

#define int long long
#define db double
#define mod 1000000007
#define pb push_back
#define pp pair<int,int>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=b;i>=a;i--)
#define maxn 200005
#define ss second
#define ff first
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
int inv(int a, int b){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}
void solve()
{
	int n;
	cin >> n;
	int a[n],b[n];
	rep(i,0,n)
		cin >> a[i] >> b[i];
	sort(a,a+n);
	sort(b,b+n);
	int x=n/2;
	int r = b[n/2];
	int l = a[n/2];
	if(n%2 == 0)
	{
		r += (b[n/2-1]);
		l += (a[n/2-1]);
	}
	cout << r-l+1 <<"\n";
}
signed main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}


Measured memory_bytes: 6724
#include <stdio.h>

#define T 1
#define F 0

int n,q,A[100];

int solve(int i, int m){

  if(m == 0){
    return T;
  }

  if(i >= n){
    return F;
  }

  if(solve(i+1, m)){
    return T;
  }

  if(solve(i+1, m-A[i])){
    return T;
  }

}

int main(){

  int i,mi;

  scanf("%d",&n);

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


  scanf("%d",&q);

  for(i=0;i<q;i++){
    scanf("%d",&mi);

    if((solve(0, mi)) == 1){
      printf("yes\n");
    }

    else{
      printf("no\n");
    }
  }

  

  return 0;

}



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


def main():
    n, m = map(int, input().split())
    num = [1 for _ in range(n)]
    red = [False for _ in range(n)]
    red[0] = True

    # Key Insight
    # 問題を言い換える
    # num[i] := i番目のコップに入っている水の量
    # red[i] := i番目のコップに赤い水が入っているか
    for i in range(m):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1

        if red[xi]:
            red[yi] = True

        num[xi] -= 1
        num[yi] += 1

        # 移動前のコップに入っていたのが赤い水だけだったとき
        if num[xi] == 0:
            red[xi] = False

    print(sum(red))


if __name__ == '__main__':
    main()


Measured memory_bytes: 4760
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        string s = sc.Next();

        long[] count = new long[3];

        foreach (var c in s)
        {
            count[c - 'a']++;
        }

        bool ok = count.Max() - count.Min() <= 1;

        string answer = ok ? "YES" : "NO";

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 26632
s=str(input())
if(s=='SUN'):
  print(7)
elif(s=='MON'):
  print(6)
elif(s=='TUE'):
  print(5)
elif(s=='WED'):
  print(4)
elif(s=='THU'):
  print(3)
elif(s=='FRI'):
  print(2)
elif(s=='SAT'):
  print(1)

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

int main() {
    int n;cin>>n;
    int a[n],b[n];
    for (int i=0;i<n;i++) {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b,b+n);
    for (int i=0;i<n;i++) {
        if (a[i]<b[n/2])
            cout<<b[n/2]<<endl;
        else
            cout<<b[n/2-1]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

int mxbit(long n){
  int c=0;
  while(n>=1){
    n/=2;
    c++;
  }
  return c;
}

int main(){
  int n;
  cin >> n;
  map<int, int>m;
  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    m[-a]++;
  }
  int ret=0;
  for(pair<int, int>p: m){
    if(m[p.first]==0)continue;
    int a=-p.first;
    int ra=(1<<mxbit(a))-a;
    if(ra==0)ra=a;
    int d;
    if(a==ra)d=m[-a]/2;
    else d=min(m[-a], m[-ra]);
    ret+=d;
    m[-a]-=d;
    m[-ra]-=d;
  }
  cout << ret;
  return 0;
}

Measured memory_bytes: 18944
#include <iostream>
#include <vector>
#include <climits>
using namespace  std;

void fnInput(vector<int> &rvnBSort, int &rnMaxElm)
{
  int nMaxSiz;
  cin >> nMaxSiz;

  rnMaxElm = 0;
  rvnBSort.resize(nMaxSiz);
  for (int i = 0; i < nMaxSiz; i++)
  {
    cin >> rvnBSort[i];
    rnMaxElm = max(rnMaxElm, rvnBSort[i]);
  }
}

void fnCntSort(const vector<int> &cnrvnBSort,vector<int> &rvnASort, int nMaxElm)
{
  vector<int> vnCnt;
  vnCnt.resize(nMaxElm);

  for (int i = 0; i < cnrvnBSort.size(); i++)
    vnCnt[cnrvnBSort[i]]++;

  for (int i = 1; i <= nMaxElm; i++)
    vnCnt[i] += vnCnt[i - 1];

  for (int i = cnrvnBSort.size() - 1; i >= 0; i--)
  {
    rvnASort[vnCnt[cnrvnBSort[i]] - 1] = cnrvnBSort[i];
    vnCnt[cnrvnBSort[i]]--;
  }
}

void fnResult(const vector<int> &cnrvnASort)
{
  for (int i = 0; i < cnrvnASort.size(); i++)
  {
    if (i)  cout << " ";
    cout << cnrvnASort[i];
  }
  cout << endl;
}

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

  int nMaxElm;
  vector<int> vnBSort, vnASort;

  fnInput(vnBSort, nMaxElm);
  vnASort.resize(vnBSort.size());

  fnCntSort(vnBSort, vnASort, nMaxElm);
  fnResult(vnASort);

  return 0;
}

Measured memory_bytes: 16808
import java.util.Scanner;

class Main{
  public static void main(String[] args) {
    
      Scanner sc = new Scanner(System.in);
      
      int n = sc.nextInt();
      
      int x1,x2,x3;
      
      for(int i = 1; i <= n; i++){
          x1 = i / 10;
          x2 = i / 100;
          x3 = i / 1000;
     
        if(i % 3 == 0 || i % 10 == 3 || x1 % 10 == 3 || x2 % 10 == 3 || x3 % 10 == 3){
        	
          System.out.print( " " + i );
          
        }
      }
	System.out.println();
  }
}

Measured memory_bytes: 28668
#include <iostream>
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int,int>;
using ll = long long;
const int INF = 100000;




int main() {
    ll n,Y;
    int x = -1;
    int y = -1;
    int z = -1;
    cin >> n >> Y;
    bool flag = false;
    rep(i,n+1){
        rep(j,n-i+1){
            if(10000*i+5000*j+1000*(n-i-j)==Y) {
                x = i; y = j; z = n-i-j;
            }
        }
    }
    cout << x << " " << y << " " << z << endl;
}



Measured memory_bytes: 256
from fractions import Fraction
from collections import defaultdict
def resolve():
    # A1*A2 + B1*B2 = 0 式変形 A1/B1 = -(B2/A2)
    # a, b の0がある条件を考える
    
    MOD = 1000000007
    N = int(input())
    zeroes = 0
    hash1 = defaultdict(int) #
    hash2 = defaultdict(str) #中の悪い相手を記入
    for _ in range(N):
        a, b = map(int, input().split())
        if a==0 and b==0:
            zeroes += 1
        elif b == 0:
            hash1["1/0"] += 1
            hash2["1/0"] = "0/1"
        elif a == 0:
            hash1["0/1"] += 1
            hash2["0/1"] = "1/0"
        else: # a, bが0以外
            rat1 = Fraction(a, b)
            rat2 = Fraction(-b, a)
            hash1[str(rat1)] += 1
            hash2[str(rat1)] = str(rat2) # 相手を入れる

    confirmed = set()
    ans = 1
    for k, v in hash1.items():
        if k in confirmed: # 確認済みを数えないようにする
            continue
        bad = hash1.get(hash2[k], 0) # 中の悪い相手, キーがなかったら0を出力
        cnt1 = pow(2, v, MOD) - 1
        cnt2 = pow(2, bad, MOD) - 1
        ans = (ans * (cnt1 + cnt2 + 1)) % MOD
        # 確認済みにする
        confirmed.add(k)
        confirmed.add(hash2[k])
        # ※ ループ中に値を変更したらエラー
        # hash1[k] = -1

    ans = (ans + zeroes + MOD -1) % MOD
    print(ans)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 119056
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    vector<ll> A(N);

    rep(i,N){
        cin>>A[i];
    }
    vector<ll>L(N+1);
    vector<ll>R(N+1);
    L[0] = 0;
    rep(i,N){
        L[i+1]=gcd(L[i],A[i]);
    }

    R[0] = 0;
    rep(i,N){
        R[i+1]=gcd(R[i],A[N-i-1]);
    }
    ll ans = 0;
    rep(i,N){
        chmax(ans,gcd(L[i],R[N-i-1]));
    }

    cout<<ans<<endl;
    return 0;
    

}

Measured memory_bytes: 5576
#!/usr/bin/env python3
import numpy as np


def solve(N, M, X, C, A):
    answer = float("inf")
    for ptn in range(1, 1 << len(C)):
        buy = [ptn & 1 << i == 1 << i for i in range(len(C))]
        if (A[buy].sum(axis=0).min() >= X) and (
            C[buy].sum() < answer
        ):
            answer = C[buy].sum()

    if answer == float("inf"):
        return -1

    return answer


def main():
    N, M, X = map(int, input().split())
    C = [None for _ in range(N)]
    A = [None for _ in range(N)]
    for i in range(N):
        C[i], *A[i] = map(int, input().split())
    C = np.array(C, dtype=np.uint32)
    A = np.array(A, dtype=np.uint32)
    answer = solve(N, M, X, C, A)
    print(answer)


if __name__ == "__main__":
    main()


Measured memory_bytes: 27356
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    a = LI()
    for i in a:
        if i & 1:
            continue
        if i % 3 == 0 or i % 5 == 0:
            continue
        else:
            print("DENIED")
            return
    print("APPROVED")
    return


#main
if __name__ == '__main__':
    solve()


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

int main() {
  int a, b;
  cin >> a >> b;
  
  int sum = a, count = 1;

  while (sum < b){
    sum += a-1;
    count++;
  }
  
  if (b == 1){
    cout << 0 << endl;
  }
  else {
    cout << count << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define maxn	500005
#define mod		int(1e9+7)
#define db		double
#define ll		long long
#define si 		stack<int>
#define qi 		queue<int>
#define vi 		vector<int>
#define pi 		pair<int, int>
ll powmod(ll a, ll b) {
	ll res = 1; a %= mod;
	for (; b; b >>= 1)
		res = (res * ((b & 1) ? a : 1)) % mod,
		a = a * a % mod;
	return res;
}
ll gcd(ll a, ll b) {
	return b ? gcd(a, b) : a;
}
/** GRAPH
int edgenum, head[maxn], vet[2 * maxn], nxt[2 * maxn], wt[2 * maxn];
void addedge(int u, int v) {
	edgenum ++;
	vet[edgenum] = v;
	nxt[edgenum] = head[u];
	head[u] = edgenum;
}
void addedge(int u, int v, int w) {
	edgenum ++;
	vet[edgenum] = v;
	nxt[edgenum] = head[u];
	head[u] = edgenum;
	wt[edgenum] = w;

}
GRAPH **/
int a[101], b[101], c[101], d[101], num[20], ans, n, m, q;
void dfs(int x, int last) {
	if (x > n) {
		int sum = 0;
		for (int i = 1; i <= q; i ++)
			if (num[b[i]] - num[a[i]] == c[i]) sum += d[i];
		ans = max(ans, sum);
		return;
	}
	for (int i = last; i <= m; i ++)
		num[x] = i, dfs(x + 1, i);
}

using namespace std;
int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= q; i ++)
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	dfs(1, 1);
	cout << ans;
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>

typedef std::pair<int, std::pair<int, int>> EDGE;

const int N = 1e4 + 1;

int pa[N];
std::vector<EDGE> E;

void init() {
  for (int i = 0; i < N; ++i) pa[i] = i;
}

int find(int x) {
  return pa[x] == x ? x : pa[x] = find(pa[x]);
}

void unite(int x, int y) {
  int px = find(x);
  int py = find(y);
  if (px != py) pa[px] = py;
}

bool check(int x, int y) {
  int px = find(x);
  int py = find(y);
  return px == py;
}

int main() {
  int n, e;
  while (std::cin >> n >> e) {
    init();
    for (int i = 0; i < e; ++i) {
      int x, y, c;
      std::cin >> x >> y >> c;
      E.push_back({c, {x, y}});
    }
    std::sort(E.begin(), E.end());
    long long ans = 0;
    for (auto e : E) {
      int c = e.first;
      int n1 = e.second.first;
      int n2 = e.second.second;
      if (!check(n1, n2)) {
        ans += (long long)c;
        unite(n1, n2);
      }
    }
    std::cout << ans << std::endl;
  }
  return 0;
}



Measured memory_bytes: 4556
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
int main(){
  int n;
  cin>>n;
  int f[n][10];int p[n][11];
  for(int i=0;i<n;i++){
    for(int j=0;j<10;j++){
      cin >> f[i][j];
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<11;j++){
      cin >> p[i][j];
    }
  }
  string s;int ans=-1000000000;int sum=0;int c[n];
  for(int i=1;i<=1023;i++){
    for(int l=0;l<n;l++) c[l]=0;
    stringstream jo;
    jo<< static_cast<std::bitset<10>>(i);
    s=jo.str();
    for(int j=0;j<n;j++){
      for(int k=0;k<10;k++){
        if(s[k]=='1'&&f[j][k]==1) c[j]++;
      }
    }
    for(int i=0;i<n;i++){
      sum+=p[i][c[i]];
    }
    ans=max(sum,ans);sum=0;
  }
  cout << ans <<endl;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    ll n; cin>>n;
    map<string,ll>mp;
    ll ans=0;
    rep(i,n){
        string s; cin>>s;
    sort(s.begin(),s.end());
    mp[s]++;
    ans+=mp[s]-1;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef long double ld;

#define rc(s) return cout << s, 0
#define fi first
#define se second
#define L (nod << 1)
#define R (L | 1)
#define smax(X, Y) ((X) > (Y) ? (X) : (Y))
#define smin(X, Y) ((X) < (Y) ? (X) : (Y))

const ll inf = (1LL<<62);
const int iinf = (1<<30);
//CLOCKS_PER_SEC

int fv[110];
int ans;

int main(){
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //ifstream cin ("test.in");
    //ofstream cout ("test.out");
	int n, k;
	cin >> n >> k;
	for (int i=1; i<=k; i++){
		int nr;
		cin >> nr;
		for (int j=1; j<=nr; j++){
			int x; cin >> x;
			fv[x]++;
		}
	}
	for (int i=1; i<=n; i++)
		if (!fv[i]) ans++;
	cout << ans;
    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> v(n);
    for (int i = 0; i < n; ++i) {
        int t, d;
        scanf("%d %d", &t, &d);
        v[t-1].emplace_back(d);
    }
    for (int i = 0; i < n; ++i) {
        sort(v[i].begin(), v[i].end(),greater<>());
    }
    vector<ll> a, b;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < v[i].size(); ++j) {
            if(j == 0) a.emplace_back(v[i][j]);
            else b.emplace_back(v[i][j]);
        }
    }
    sort(a.begin(), a.end(), greater<>());
    sort(b.begin(), b.end(), greater<>());
    vector<ll> A(n+1,0), B(n+1,0);
    for (int i = 0; i < n; ++i) {
        A[i+1] = A[i]+(i < a.size() ? a[i] : 0);
    }
    for (int i = 0; i < n; ++i) {
        B[i+1] = B[i]+(i < b.size() ? b[i] : 0);
    }
    ll ans = 0;
    for (ll i = 1; i <= min((int)a.size(), k); ++i) {
        ans = max(ans, A[i]+B[k-i]+i*i);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 8180
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;

int gcd(int a,int b){
  int min,max;
  if(a > b){
    max = a;
    min = b;
  }
  else{
    max = b;
    min = a;
  }
  if(max % min == 0){
    return min;
  }
  else{
    return gcd(min,max % min);
  }
}
int main(){
  int a,b,k,ii,g,n;
  int aOk[101],bOk[101];
  cin >> a >> b >> k;
  //cout << gcd(a,b) << endl;
  g = gcd(a,b);
  n = 0;
  for(ii=1;ii<=100;ii++){
    if(a % ii == 0){
      aOk[ii] = 1;
    }
    else{
      aOk[ii] = 0;
    }
    if(b % ii == 0){
      bOk[ii] = 1;
    }
    else{
      bOk[ii] = 0;
    }
  }

  for(ii=100;ii>=1;ii--){
    if(aOk[ii] == 1 && bOk[ii] == 1){
      n++;
      if(n == k){
	break;
      }
    }
  }
  cout << ii << endl;
  return 0;
}


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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	double cnt=0;
	vector<double>v(3);
	for(int i=0;i<3;i++)cin>>v.at(i);
	sort(v.begin(),v.end(),greater<double>());
	if(v.at(1)==v.at(2)){
		cnt+=v.at(0)-v.at(1);
	}else{
		cnt+=v.at(0)-v.at(1);
		v.at(1)=v.at(0);
		v.at(2)+=cnt;
		cnt+=(v.at(0)-v.at(2))/2;
		if(fmod((v.at(0)-v.at(2)),2)!=0){
			cnt+=2;
		}
	}
	cout<<floor(cnt)<<endl;

}


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

using namespace std;

const int MAX_V = 101;
vector<int> G[MAX_V];

int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        if (a == 0 && b == 0) {
            G[1].push_back(2);
            G[2].push_back(1);

            bool flag = true;
            for (int i = 1; i < MAX_V; i++) {
                if (G[i].size() % 2) flag = false;
                G[i].clear();
            }
            
            if (flag) puts("OK");
            else puts("NG");

            continue;
        }

        G[a].push_back(b);
        G[b].push_back(a);
    }

    return 0;
}


Measured memory_bytes: 3148
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
const int INF=100000000;
long long int X,Y;
int c;
int main(){
  cin >> X >> Y;
  long long int a=X;
  while(a<=Y){
    c++;
    a*=2;
  }
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 256
N,K=map(int, input().split())

MOD = 10**9+7
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value += Mint.get_value(other)
        if self.value >= MOD: self.value -= MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value -= Mint.get_value(other)
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

ans = Mint()
for i in range(K,N+2):
    mn = Mint(i*(i-1)//2)
    mx = Mint((N+N-i+1)*i//2)
    ans += mx - mn + 1
print(ans)


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

typedef long long ll;
using namespace std;

const ll MAXN = (ll)1e5+10;
ll dp[MAXN][3];

int main(void) {
   ll N;
   cin>>N;
   ll h[N][3];
   rep(i,N) {
      cin>>h[i][0];
      cin>>h[i][1];
      cin>>h[i][2];
   }
   memset(dp,0,sizeof(dp));
   rep(i,3) dp[0][i] = h[0][i];
   for (int i = 1; i < N;i++) {
      dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + h[i][0];
      dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + h[i][1];
      dp[i][2] = max(dp[i-1][1],dp[i-1][0]) + h[i][2];
   }
   // rep(i,N) cout<<dp[i]<<endl;
   ll ans;
   ans = max(max(dp[N-1][0],dp[N-1][1]),dp[N-1][2]);
   cout<<ans<<endl;





   return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

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

    rep(i, h) {
        rep(j, w) {
            cout << ((i < b)^(j < a) ? 0 : 1);
        }
        cout << "\n";
    }

    return 0;
}

Measured memory_bytes: 1280
S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0 for _ in range(13)]
pp = [0 for _ in range(13)]

dp[0] = 1
for i in range(N):
    pp, dp = dp, pp
    for d in range(13):
        dp[d] = 0
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])


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

const int mod = 1e9+7;

int main() {
    int N,M;
    cin >> N >> M;
    vector<ll> dp(N+1, -1);
    dp[0]=1;
    dp[1]=1;
    int a;
    for(int i=0;i<M;++i) {
        cin >> a;
        dp[a] = 0;
    }
    for(int i=2;i<=N;++i) {
        if(dp[i]==0) continue;
        dp[i] = (dp[i-2]+dp[i-1])%mod;
    }
    cout << dp[N] << endl;
    
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define ll long long
using namespace std;
vector<string> split(const string &str, char sep){
    std::vector<std::string> v;
    auto first = str.begin();
    while(first != str.end()){
        auto last = first;
        while(last != str.end() && *last != sep) ++last;
        v.push_back(std::string(first,last));
        if(last!=str.end()) ++last;
        first=last;
    }
    return v;
}
int n,k,l;
vector<vector<int>> e1(200000),e2(200000);
int v1[200000],v2[200000];  //連結成分リスト
vector<ll> p;     //二重連結成分リスト
void dfs1(int i, int j){
    v1[i]=j+1;
    for (auto v:e1[i]){
        if (v1[v]==0) dfs1(v,j);
    }
}
void dfs2(int i, int j){
    v2[i]=j+1;
    for (auto v:e2[i]){
        if (v2[v]==0) dfs2(v,j);
    }
}
int main(){
    cin>>n>>k>>l;
    rep(i,k){
        int p,q;
        cin>>p>>q;
        p-=1;q-=1;
        e1[p].push_back(q);
        e1[q].push_back(p);
    }
    rep(i,l){
        int p,q;
        cin>>p>>q;
        p-=1;q-=1;
        e2[p].push_back(q);
        e2[q].push_back(p);
    }
    rep(i,n){
        if (v1[i]==0) dfs1(i,i);
        if (v2[i]==0) dfs2(i,i);
    }
    
    rep(i,n){
        p.push_back(v1[i]*200001+v2[i]);
    }
    sort (p.begin(),p.end());
    rep(i,n){
        int lb=lower_bound(p.begin(),p.end(),v1[i]*200001+v2[i])-p.begin();
        int ub=upper_bound(p.begin(),p.end(),v1[i]*200001+v2[i])-p.begin();
        cout<<ub-lb;
        if (i==n-1) cout<<endl;
        else cout<<" ";
    }
    return 0;
}

Measured memory_bytes: 20212
from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]

d = defaultdict(int)

d[0] = 1
sum = 0
for i in range(N):
    sum += A[i]
    d[sum] += 1

ans = 0
for v in d.values():
    if v >= 2:
        ans += (v*(v-1))//2

print(ans)


Measured memory_bytes: 111440
#include<iostream>
#include<vector>
#include<limits>
using namespace std;

int MAX_INT = numeric_limits<int>::max();
int N;
vector<int> vec6, vec9;

int getMinTimes(int n, int idx6, int idx9) {
  if (n < 6) return n;

  while (1) {
    if (idx6 == -1) break;
    if (vec6[idx6] <= n) break;
    idx6 -= 1;
  }
  
  while (1) {
    if (idx9 == -1) break;
    if (vec9[idx9] <= n) break;
    idx9 -= 1;
  }

  int buf6 = MAX_INT, buf9 = MAX_INT;
  if (idx6 != -1) buf6 = getMinTimes(n - vec6[idx6], idx6, idx9);
  if (idx9 != -1) buf9 = getMinTimes(n - vec9[idx9], idx6, idx9);
  
  if (buf6 < buf9) return buf6 + 1;
  else return buf9 + 1;
}

int main() {
  scanf("%d", &N);
  
  int base;

  base = 1;
  while (base * 6 <= N) {
    base *= 6;
    vec6.push_back(base);
  }

  base = 1;
  while (base * 9 <= N) {
    base *= 9;
    vec9.push_back(base);
  }

  int idx9 = vec9.size() - 1, idx6 = vec6.size() - 1;
  printf("%d\n", getMinTimes(N, idx6, idx9));

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <iomanip>
using namespace std;
#pragma warning(disable:4996)

int main()
{
	int n;
	cin >> n;
	vector<int>a(n);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	sort(a.begin(), a.end());
	sum -= a[n - 1];
	int mx = a[n - 1];
	if (mx < sum)cout << "Yes";
	else cout << "No";
}


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

using namespace std;
#define int long long

signed main(){
    string N;
    cin >> N;
    
    int cnt = 0;
    for(int i=0;i<4;i++){
        if(N[i] == '2') cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>

const int seat[4]{ 6000, 4000, 3000, 2000 };

int t, n;

int main()
{
	for (int i = 0; i < 4; i++)
	{
		scanf("%d", &t);
		scanf("%d", &n);

		printf("%d\n", seat[t - 1] * n);
	}

	return 0;
}

Measured memory_bytes: 2696
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
ll f(ll k,ll a,ll b)
{
    ll s=0;
        if(b<0)
        {
            a=-a;b=-b;
            ll t=a;
            a=b;
            b=t;
        }
        s=b/k-a/k;
        if(a%k==0||a<=0)
           s++;
           return s;
}
int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;

    ll m=gcd(c,d);
    m=c*d/m;
    ll sum=b-a+1;
    sum-=f(c,a,b);
    sum-=f(d,a,b);
    sum+=f(m,a,b);
    cout<<sum;
    return 0;

}


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

#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)
int main(){
	long long N,count = 0;
  cin >> N;
  vector<int> stick(N);
  froop1(0,N) cin >> stick.at(i);
  sort(stick.begin(),stick.end(),greater<int>());
  froop1(0,N){
    for(int j = i + 1;j < N;j++){
    for(int k =j + 1;k < N;k++){
      if(stick.at(i) < stick.at(j) + stick.at(k)){
        count++;
      }else{
        break;
      }
    }
    }
  }
  cout << count << endl;
return 0;
}

Measured memory_bytes: 3616