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

using namespace std;

long long ban;

struct Edge{
	int u , v , c;
}seq[300];

long long f[1 << 15] , n , m , Fa[20] , dp[1 << 15][15][2] , Cost[20][20] , BestCut[15][1 << 15];

inline int find_fa( int u ){
	return Fa[u] != u ? Fa[u] = find_fa( Fa[u] ) : u;
}

void Union_Set( int u , int v ){
	int p1 = find_fa( u ) , p2 = find_fa( v );
	if( p1 != p2 )
		Fa[p1] = p2;
}

inline void upd( long long & x , long long y ){
	x = max( x , y );
}

long long Ans = 0;

int main( int argc , char * argv[] ){
	scanf( "%d%d" , & n , & m );
	memset( f , 0x80 , sizeof( f ) );
	memset( dp , 0x80 , sizeof( dp ) );
	memset( Cost , 0x80 , sizeof( Cost ) );
	memset( BestCut , 0x80 , sizeof( BestCut ) );
	ban = dp[0][0][0];
	for(int i = 1 ; i <= m ; ++ i){
		scanf( "%d%d%d" , & seq[i].u , & seq[i].v , & seq[i].c );
		-- seq[i].u , -- seq[i].v;
		Cost[seq[i].u][seq[i].v] = Cost[seq[i].v][seq[i].u] = seq[i].c;
		Ans += seq[i].c;
	}
	for(int i = 0 ; i < n ; ++ i)
		for(int mask = 0 ; mask < (1 << n) ; ++ mask){
			long long has = 0;
			for(int j = 0 ; j < n ; ++ j)
				if( ( mask >> j & 1 ) && Cost[i][j] != ban )
					has += Cost[i][j];
			if( has )
				upd( BestCut[i][mask] , has );
		}
	for(int mask = 1 ; mask < (1 << n) ; ++ mask){
		for(int i = 0 ; i < n ; ++ i) Fa[i] = i;
		long long ret = 0;
		for(int i = 1 ; i <= m ; ++ i)
			if( ( mask >> seq[i].u & 1 ) && ( mask >> seq[i].v & 1 ) ){
				Union_Set( seq[i].u , seq[i].v );
				ret += seq[i].c;
			}
		set < int > wr;
		for(int i = 0 ; i < n ; ++ i)
			if( mask >> i & 1 )
				wr.insert( find_fa( i ) );
		f[mask] = ret;
	}
	dp[1][0][0] = 0;
	for(int mask = 0 ; mask < (1 << n) ; ++ mask)
		for(int i = 0 ; i < n ; ++ i)
			for(int j = 0 ; j < 2 ; ++ j)
				if( dp[mask][i][j] != ban ){
					for(int v = 0 ; v < n ; ++ v)
						if( ( mask >> v & 1 ) == 0 && Cost[i][v] != ban  )
							upd( dp[mask | (1 << v)][v][0] , dp[mask][i][j] + Cost[i][v] );
					if( j == 0 ){
						int z = (1 << n) - 1 - mask;
						for(int v = z ; v ; v = (v - 1) & z)
							upd( dp[mask | v][i][1] , dp[mask][i][j] + f[v] + max( 0LL , BestCut[i][v] ) );
					}
				}
	long long ret = ban;
	for(int mask = 0 ; mask < (1 << n) ; ++ mask){
		upd( ret , dp[mask][n - 1][0] );
		upd( ret , dp[mask][n - 1][1] );
	}
	printf( "%lld\n" , Ans - ret );
	return 0;
}

Measured memory_bytes: 12032
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;
using ll = long long ;
using P = pair<ll,ll>;
ll INF = 1000000007;
// ll INF = 9223372036854775807;
// ll INF = 998244353;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    string s;
    cin >> s;
    s.erase(3);
    cout << s << endl;
}

Measured memory_bytes: 3596
k()=readline()|>chomp
s()=[parse(Int,x)for x=k()|>split]
n,q=s()
t=k()
a=zeros(Int,n)
c=0
for j=2:n
c+=t[j-1:j]=="AC"
a[j]=c
end
for i=1:q
l,r=s()
println(a[r]-a[l])
end

Measured memory_bytes: 154608
import math
N, K = map(int, input().split())

A_array = list(map(int, input().split()))

# print(A_array)

A_sum = sum(A_array)

candidate_array = []

for i in range(1, int(math.sqrt(A_sum))+1):
    if A_sum % i == 0:
        candidate_array.append(i)
        if A_sum // i != i:
            candidate_array.append(A_sum//i)

candidate_array.sort()

ans = 0

for check_num in candidate_array:
    q_array = [a % check_num for a in A_array]
    q_array.sort()
    # print(q_array)
    start = 0
    rest = N * check_num - sum(q_array)
    for q in q_array:
        start += q
        rest -= (check_num-q)
        # print(start,rest)
        if start == rest:
            break
    if start <= K:
        ans = max(ans, check_num)

print(ans)


Measured memory_bytes: 41708
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N;i++){
    cin >> A.at(i);
  }
  sort(A.begin(), A.end());
  
  int sum = 0;
  for(int i = N-1; i > 0 ;i-=2){
    sum += A.at(i) - A.at(i-1);
  }
  if(N%2==1) sum += A.at(0);
  
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
import bisect
import sys
S = input()
T = input()


# sが何番目に出てくるかの辞書をついくる
s_index = {}
for i in range(len(S)):
    if S[i] in s_index:
        s_index[S[i]].append(i + 1)
    else:
        s_index[S[i]] = [i+1]


current_s_index = 0
loop_count = 0
ans = 0
for t in T:
    if not t in s_index:
        print(-1)
        sys.exit()

    if current_s_index >= s_index[t][-1]:
        current_s_index = s_index[t][0]
        loop_count += 1
    else:
        index = bisect.bisect(s_index[t], current_s_index)
        current_s_index = s_index[t][index]

print(current_s_index + loop_count * len(S))



Measured memory_bytes: 46192
#include <iostream>
#include <cstdio>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <utility>
#include <string>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;
using ll=long long;
using vint=vector<int>;
using pint=pair<int,int>;

const double EPS = 1e-9;
const int inf = numeric_limits<int>::max();

#define rep(i,n) for(int i=0;i<int(n);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define SHOW(a) cout << #a << " = " << a << endl
#define ARR(a,i,n) for(int i=0;i<int(n);++i) cout << #a << "[" << i << "]" << " = " << a[i] << endl

void solve(){
	string N;
	cin >> N;
	int i = 0;
	for(char t : N){
		i += t - '0';
	} 
	int j = N[0] - '0' - 1 + 9 * int(N.size() - 1);
	cout << max(i, j) << endl;
}

int main(){
	solve();
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

		while (true) {

			int n = scan.nextInt();
			int count = 0;
			
			if (n == 0)
				break;

			for (int i = 1; i < n; i++) {
				int sum = 0;
				int j = i;
				while(sum<n){
					sum+=j;
					if(sum==n)count++;
					j++;
				}

			}
			System.out.println(count);
		}
		scan.close();
	}
}

Measured memory_bytes: 19908
n= int(input())
dp=[0]*3

for day in range(n):
     points=list(map(int,input().split()))

     new_dp=[0]*3
     for i in range(3):
          for j in range(3):
               if j!=i:
                    new_dp[j]= max(new_dp[j],dp[i]+points[j])
     dp=new_dp
print(max(dp))





Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
#define rep(i, s, n) for(int i = s; i < n; i++)
#define ll long long

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    vector<int> b(n);
    rep(i, 0, n+1) cin >> a[i];
    rep(i, 0, n) cin >> b[i];

    ll ans = 0;
    rep(i, 0, n) {
        int flag = 0;
        if(a[i]-b[i] < 0) {
            ans += a[i];
            b[i] -= a[i];
            a[i] = 0;
            flag = 1;
        }
        else {
            ans += b[i];
            a[i] -= b[i];
            b[i] = 0;
        }
        //cout << a[i] << " " <<b[i] << endl;
        if(flag == 1) {
            if(a[i+1]-b[i] < 0) {
                ans += a[i+1];
                a[i+1] = 0;
                b[i] = 0;
            }
            else {
                ans += b[i];
                a[i+1] -= b[i];
            }
        }

    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a, int b) {  
  return b != 0 ? gcd(b, a % b) : a;
}//MAX
int lcm(int a, int b) { 
   return a * b / gcd(a, b);
   }
//MIN

 main() {
   int n;
   cin >> n;
   vector<int>a(n),b(n);
   for(int i=0;i<n;i++){
     cin >> a.at(i);
     b.at(i)=a.at(i);
   }
   sort(b.begin(),b.end());
   reverse(b.begin(),b.end());
   for(int i=0;i<n;i++){
     if(a.at(i)==b.at(0))cout<<b.at(1)<<endl;
     else cout<<b.at(0)<<endl;
   }
   
 }

Measured memory_bytes: 3200
#include <iostream>
using namespace std;
int nr, n, per_d;
int main()
{
    cin>>n;
    for(int p=1; p<n; p++)
    {
        for(int d=1; d*d<=p; d++)
            if(p%d==0)
            {
                per_d=p/d;
                if(per_d!=d) nr=nr+2;
                else nr++;
            }

    }
    cout<<nr;
    return 0;
}


Measured memory_bytes: 3644
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a) 

for i in range(m):
  max_ = -heapq.heappop(a)
  d = max_ // 2
  heapq.heappush(a, -d)

c = 0
for i in range(len(a)):
  c -= heapq.heappop(a)
print(c)


Measured memory_bytes: 74264
def divideprime(n):
    ret = []
    i = 2
    while i*i <= n:
        cnt = 0
        if(n%i != 0):
            i += 1
            continue
        
        while n % i == 0:
            cnt += 1
            n //= i
        
        ret.append([i,cnt])
        
        i += 1
    
    if n != 1:
        ret.append([n,1])
    
    return ret
    
N = int(input())

divp = divideprime(N)

ans = 0
for t in divp:
    cnt = 0
    e = 0
    s = set([])
    while (t[1]-e > 0) and (t[1]-e not in s):
        ans += 1
        cnt += 1
        e += cnt
        s.add(cnt)

print(ans)

Measured memory_bytes: 62556
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long i = 0; i < n; i++)
#define erep(i, n) for(long i = 1; i <= n; i++)
const long MOD = 1000000007;

int main() {long N, M;
cin >> N;
vector<long> t(N + 1);
erep(i, N) cin >> t.at(i);
cin >> M;
vector<long> p(M + 1); vector<long> x(M + 1);
erep(i, M) cin >> p.at(i) >> x.at(i);
long ans = 0;
erep(i, N) ans += t.at(i);
erep(i, M){
    cout << ans - t.at(p.at(i)) + x.at(i) << endl;
}



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



Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 315;
const int MM = 1000000007;

int main()
{
	int N, Q;
	scanf("%d%d", &N, &Q);
	for(int t = 1; t <= Q; t++){
		int a, b;
		scanf("%d%d", &a, &b);
		if( N == 1 ) printf("%d\n", a);
		else{
			while(a != b){
				if( a > b ) swap(a, b);
				b = (b+N-2)/N;
			}
			printf("%d\n", a);
		}
	}
}


Measured memory_bytes: 1280
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define _USE_MATH_DEFINES
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0,1,0,-1 };
const ll dy[4] = { -1, 0, 1,0 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
double mysqrt(double x) {
	double l = 0, r = x;
	for (int i = 0; i < 64; ++i) {
		double m = (l + r) / 2.0;
		if (m*m < x)l = m;
		else r = m;
	}
	return l;
}
///////////////////////////////////////

int main() {
	ll n; cin >> n;
	ll a[100100];
	ll ans = 0;
	ll ans2 = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		ans = ans ^ a[i];
	}
	if (ans == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;
import java.util.HashSet;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		HashSet<Integer> set=new HashSet<>();
		for(int i = 0; i<n; i++){
			set.add(sc.nextInt());
		}
		System.out.println(set.size());
	}
}

Measured memory_bytes: 22996
/*
h3110_fr13nd,
 
AUTHOR : @sam_jn
*/
 
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<pair<int, int>, null_type, less_equal<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define boost ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define MOD 1000000007
#define pb push_back
#define ff first
#define ss second
#define NN 1000002
#define in(a, n) for(int i = 0; i < n; i++) cin >> a[i];
#define ot(a, n) for(int i = 0; i < n; i++) cout << a[i] << " ";
#define ot2(a, n) for(int i = 0; i < n; i++) cout << a[i] << "\n";
ll pwr(ll a, ll b);
ll pwr(ll a, ll b, ll m);
int baap[200002];
int prime[NN];
int find(int i);  
bool Union(int x, int y);
ll inv(ll x) {return pwr(x, MOD - 2, MOD);}
void init();
ll max(ll x, ll y, ll z) {return max(x, max(y, z));}
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {-1, 1, 0, 0, 1, -1, 1, -1};
//----------------------------------SOLUTION-BELOW-------------------------------------------// 

void solve(){
    int n;
    cin >> n;
    ll dp[n + 1] = {0};
    for(int x = 1; x <= n; x++){
        ll val1 = x * x;
        if(val1 > n) break;
        for(int y = 1; y <= n; y++){
            ll val2 = val1 + y*y + x*y;
            if(val2 > n) break;
            for(int z = 1; z <= n; z++){
                ll val3 = val2 + z*z + x*z + y*z;
                if(val3 > n) break;
                else dp[val3]++;
            }
        }
    }
    for(int i = 1; i <= n; i++) cout  << dp[i] << "\n";
    
}
int main(){


                                                            #ifndef ONLINE_JUDGE    
                                                            freopen("/home/samyak/Desktop/CP/input.txt", "r", stdin);
                                                            freopen("/home/samyak/Desktop/CP/output2.txt", "w", stdout);
                                                            #else
                                                            // online submission
                                                            #endif
// 

    boost
    int _ = 1;
    // cout << 0 << endl;
    // cin >> _;
    while(_--){
        solve();
        cout << endl;
    }
}
 
 
//--------------------------------------DEFININTIONS---------------------------------------
ll pwr(ll a, ll b){
    if(b == 0)
        return 1 ;
    ll c = pwr(a, b/2) ;
    c = c * c;
    if(b % 2)
        return c*a;
    return c ;
}
ll pwr(ll a, ll b, ll m){
    if(b == 0)
        return 1;
    ll c = pwr(a, b/2, m) % m ;
    c = (c * c) % m;    
    if(b % 2)
        return (c * a%m) % m;
    return c ;
}
int find(int i)  
{  
    if (baap[i] != i)  
        baap[i] = find(baap[i]);  
  
    return baap[i];  
}
 
bool Union(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return false;
    baap[x] = y;
    return true;
}
void init(){
  for(ll i = 2; i < NN; i++){
      if(prime[i]) continue;
      for(ll j = 2*i; j < NN; j += i)
          prime[j] = i;
  }
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int n,m;
  cin>>n>>m;
  static int dp[2][101][101*101];
  memset(dp,-1,sizeof(dp));
  dp[0][0][0]=0;
  for(int i=0;i<n;i++){
    int a,b,c;
    cin>>a>>b>>c;
    bool f=i%2;
    for(int j=0;j<101;j++)
      for(int k=0;k<101*101;k++)
	dp[!f][j][k]=-1;
    for(int j=0;j<101;j++){
      for(int k=0;k<101*101;k++){
	if(dp[f][j][k]<0) continue;
	dp[!f][j][k]=max(dp[!f][j][k],dp[f][j][k]);
	if(j+c>m) continue;
	dp[!f][j+c][k+a]=max(dp[!f][j+c][k+a],dp[f][j][k]+b);
	dp[!f][j+c][k+b]=max(dp[!f][j+c][k+b],dp[f][j][k]+a);
      }
    }
  }
  int ans=0;
  for(int i=0;i<=m;i++)
    for(int k=0;k<101*101;k++)
      ans=max(ans,min(k,dp[n%2][i][k]));
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 11128
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n+1];
    REP(i,n){
        cin>>a[i+1];
    }
    vector<int> b;
        for(int i=n;i>0;i-=2){
            b.push_back(a[i]);
        }
        //MX奇数なら２開始
        for(int i=2-(n+1)%2;i<n;i+=2) {
            b.push_back(a[i]);
        }

    REP(i,b.size()){
        cout<<b[i]<<" ";
    }
    cout<<endl;

    return 0;
}

Measured memory_bytes: 3828
#include<stdio.h>
#define M 1000000
int main(){
  char p[M]={1,1};
  int i,j,n,m,d[31];
  for(i=2;i*i<M;i++){
    if(p[i])continue;
    for(j=2;i*j<M;j++){
      p[i*j]=1;
    }
  }
  while(scanf("%d %d",&n,&m),n||m){
    char a[M]={0};
    for(i=0;i<n;i++){
      scanf("%d",&d[i]);
      a[d[i]]=1;
    }
    for(i=0;i<m;i++){
      if(a[i]==0)continue;
      for(j=0;j<n;j++){
	if(m<i+d[j])continue;
	a[i+d[j]]=1;
      }
    }
    for(i=m;i;i--){
      if(a[i]&&p[i]==0)break;
    }
    if(i)printf("%d\n",i);
    else printf("NA\n");
  }
  return 0;
}

Measured memory_bytes: 2572
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    vector<int> x(N), y(M);
    x.push_back(X);
    y.push_back(Y);
    for (int i = 0; i < N; i++) cin >> x[i];
    for (int i = 0; i < M; i++) cin >> y[i];
    if (*max_element(x.begin(), x.end()) < *min_element(y.begin(), y.end())) {
        puts("No War");
    }
    else {
        puts("War");
    }
}

Measured memory_bytes: 256
import math
A,B,H,M = list(map(int,input().split()))

ang_h = (H + M/60)* 30
ang_m = M * 6
c = 0
ang = abs(ang_m - ang_h)
if ang >=180:
	ang = 360- ang
c = (A**2 + B**2 -2*A*B*math.cos(math.radians(ang)))**0.5

print(c)

Measured memory_bytes: 9504
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define REP(i,n) for(ll i = 0; i < (n); ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,e) for (ll i = s; i < (ll)e; i++)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

template<ll mod> struct GF {
	ll v;
	GF(ll v = 0) : v((v % mod + mod) % mod) {}
	GF operator+(GF x) const { return v + x.v; }
	GF operator-(GF x) const { return v - x.v; }
	GF operator*(GF x) const { return v * x.v; }
	GF operator/(GF x) const { return x.inverse() * v; }
	GF operator+=(GF x) { return (*this) = (*this) + x; }
	GF operator*=(GF x) { return (*this) = (*this) * x; }
	GF operator-=(GF x) { return (*this) = (*this) - x; }
	GF operator/=(GF x) { return (*this) = (*this) / x; }
	GF inverse() const { // http://topcoder.g.hatena.ne.jp/iwiwi/20130105/1357363348
		ll a = v, b = mod, x = 1, y = 0;
		while (b) {
			ll t = a / b;
			swap(a -= t * b, b);
			swap(x -= t * y, y);
		}
		return x;
	}
	GF pow(ll n) const {
		ll x = v, r = 1;
		for (; n > 0; n >>= 1) {
			if (n & 1) (r *= x) %= mod;
			(x *= x) %= mod;
		}
		return r;
	}
};


int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);
	ll n; cin >> n;
	string s; cin >> s;

	vector<vector<GF<mod>>> dp(n+1, vector<GF<mod>>(n+1,0)); dp[0][s.size()] = 1;
	REP(i, n) REP(j, n + 1) {
		if(j < n) dp[i + 1][j + 1] += dp[i][j] * 2;
		if(j > 0) dp[i + 1][j - 1] += dp[i][j];
		if (j == 0) dp[i + 1][j] += dp[i][j];
	}

	cout << dp[n][0].v << endl;

	return 0;
}

Measured memory_bytes: 195840
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7;

pi a[100005];

int32_t main()
{
	IO_OP;
	
	int n, m;
	cin >> n >> m;
	for(int i=0;i<n;i++)
		cin >> a[i].F >> a[i].S;
	sort(a, a+n);
	int ans = 0;
	for(int i=0;i<n;i++) {
		int re = min(m, a[i].S);
		m -= re;
		ans += re * a[i].F;
	}
	cout << ans << endl;
}



Measured memory_bytes: 1792
import sys
import math
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
s = l()
a = s[:len(s)//2]
b = s[len(s)//2+1:]
print("Yes" if a == b else "No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
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; }
int main(){
    ll h,w; cin>>h>>w;
    vector<vector<char>> s(h,vector<char>(w));
    rep(i,h){
        rep(j,w){
            cin>>s[i][j];
        }
    }
    ll ans=0;
    vector<ll> x={1,0,-1,0},y={0,1,0,-1};
    rep(i,h){
        rep(j,w){
            if(s[i][j]=='#') continue;
            vector<vector<ll>> d(h,vector<ll>(w,-1));
            queue<vector<ll>> q;
            q.push({i,j});
            d[i][j]=0;
            while(!q.empty()){
                vector<ll> a=q.front();
                q.pop();
                rep(k,4){
                    if(a[0]+x[k]>=0 && a[0]+x[k]<h && a[1]+y[k]>=0 && a[1]+y[k]<w && s[a[0]+x[k]][a[1]+y[k]]=='.'){
                        if(d[a[0]+x[k]][a[1]+y[k]]!=-1)continue;
                        q.push({a[0]+x[k],a[1]+y[k]});
                        d[a[0]+x[k]][a[1]+y[k]]=d[a[0]][a[1]]+1;
                    }
                }
            }
            rep(k,h){
                rep(l,w){
                    chmax(ans,d[k][l]);
                }
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
use std::collections::HashMap;

#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>()
        }
    };
    (;;$n:expr) => {
        {
            (0..$n).map(|_| scan!()).collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let n = scan!(i64);
    let mut m = HashMap::new();

    for mut i in 1..n + 1 {
        for j in 2.. {
            while i % j == 0 {
                let v = m.entry(j).or_insert(0);
                *v += 1;
                i /= j
            }
            if i == 1 {
                break;
            }
        }
    }

    let mut ans = 1i64;
    for (_, v) in m.into_iter() {
        ans *= v + 1;
        ans %= 1_000_000_007;
    }
    println!("{}", ans)
}


Measured memory_bytes: 4352
package main

import (
	"bufio"
	"fmt"
	"os"
	"reflect"
	"strconv"
)

const (
	maxBufSize = 1024 * 1024
)

var (
	sc = func() *bufio.Scanner {
		sc := bufio.NewScanner(os.Stdin)
		buf := make([]byte, 1)
		sc.Buffer(buf, maxBufSize)
		sc.Split(bufio.ScanWords)
		return sc
	}()
	out = bufio.NewWriter(os.Stdout)
)

func solve(n int64, m int64, ps []int64, ss []string) (int64, int64) {
	ac := int64(0)
	wa := int64(0)
	as := make([]bool, 100001)
	ws := make([]int64, 100001)
	for i, p := range ps {
		if as[p] {
			continue
		}

		if ss[i] == "WA" {
			ws[p] ++
			continue
		}

		ac ++
		wa += ws[p]
		as[p] = true
	}

	return ac, wa
}

func main() {
	defer out.Flush()

	n := nextInt()
	m := nextInt()
	ps := make([]int64, m)
	ss := make([]string, m)
	for i := 0; i < int(m); i++  {
		ps[i] = nextInt()
		ss[i] = next()
	}
	r1, r2 := solve(n, m, ps, ss)
	fmt.Fprintln(out, r1, r2)
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextStringAsBytes() []byte {
	sc.Scan()
	return []byte(sc.Text())
}

func nextInt() int64 {
	a, _ := strconv.ParseInt(next(), 10, 64)
	return a
}

func nextFloat() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int64) []int64 {
	ret := make([]int64, n)
	for i := int64(0); i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}

func nextFloats(n int64) []float64 {
	ret := make([]float64, n)
	for i := int64(0); i < n; i++ {
		ret[i] = nextFloat()
	}
	return ret
}
func nextStrings(n int64) []string {
	ret := make([]string, n)
	for i := int64(0); i < n; i++ {
		ret[i] = next()
	}
	return ret
}

func containStr(arr []string, target string) bool {
	for _, v := range arr {
		if v == target {
			return true
		}
	}
	return false
}

func PrintOut(src interface{}, joinner string) {
	switch reflect.TypeOf(src).Kind() {
	case reflect.Slice:
		s := reflect.ValueOf(src)
		for idx := 0; idx < s.Len(); idx++ {
			fmt.Fprintf(out, "%v", s.Index(idx))
			if idx < s.Len()-1 {
				fmt.Fprintf(out, "%s", joinner)
			} else {
				fmt.Fprintln(out)
			}
		}
	default:
		fmt.Fprintln(out, "orz")
	}
}

// mapからkeysとvaluesを返す
func splitKeyValue(m map[interface{}]interface{}) (keys, values []interface{}) {
	switch reflect.TypeOf(m).Kind() {
	case reflect.Map:
		s := reflect.ValueOf(m)
		for _, v := range s.MapKeys() {
			keys = append(keys, v)
			values = append(values, s.MapIndex(v))
		}
	default:
		fmt.Fprintln(out, "orz")
	}
	return
}


Measured memory_bytes: 6020
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

ll gcd(ll n, ll m){
  if(n%m == 0) return m;
  return gcd(m, n%m);
}

ll lcm(ll n, ll m){
  return n * m / gcd(n, m);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll x, y; cin >> x >> y;
  cout << gcd(x, y) << endl;
}


Measured memory_bytes: 3144
#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>

void solve(std::string S) 
{
  std::vector<int> result(S.size(),0);
  int count_r = 0;
  int count_l = 0;
  int rl_ind = 0;
  for (int i = 0; i < S.size()-1; i++)
  {
    if(std::string(1,S[i]) == std::string("R") && 
       std::string(1,S[i+1]) == std::string("L"))
    {
      rl_ind = i;
      if(i == S.size()-2)
      {
        int r_div = count_r/2;
        int r_mod = count_r%2;
        int l_div = count_l/2;
        int l_mod = count_l%2;
        result[rl_ind] = r_div + l_div+l_mod+1;
        result[rl_ind+1] = r_div+r_mod + l_div+1;
      }
    }
    else if(std::string(1,S[i]) == std::string("L") && 
            std::string(1,S[i+1]) == std::string("R"))
    {
      int r_div = count_r/2;
      int r_mod = count_r%2;
      int l_div = count_l/2;
      int l_mod = count_l%2;
      result[rl_ind] = r_div + l_div+l_mod+1;
      result[rl_ind+1] = r_div+r_mod + l_div+1;
      count_r = 0;
      count_l = 0;
    }
    else if(i == S.size()-2 &&
            std::string(1,S[i]) == std::string("L") && 
            std::string(1,S[i+1]) == std::string("L"))
    {
      count_l += 1;
      int r_div = count_r/2;
      int r_mod = count_r%2;
      int l_div = count_l/2;
      int l_mod = count_l%2;
      result[rl_ind] = r_div + l_div+l_mod+1;
      result[rl_ind+1] = r_div+r_mod + l_div+1;
    }
    else if(std::string(1,S[i])==std::string("R"))
    {
      count_r ++;      
    }
    else if(std::string(1,S[i])==std::string("L"))
    {
      count_l ++;
    }
  }
  for(auto& a: result)
  {
    std::cout << a << " ";
  }
  
}

int main(void) 
{
  std::string S;
  std::cin >> S;
  solve(S);
  return 0;
}


Measured memory_bytes: 1024
class Main{

	public static void main (String[] args) {

		Main main = new Main();

		java.util.Scanner sc = new java.util.Scanner(System.in);

		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int K = sc.nextInt();

		boolean flag = main.calculate (A,B,C,K,0,false);

		if (flag) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

		sc.close();;

	}

	boolean calculate (int A, int B, int C, int K, int count, boolean flag) {

		if (K==count) {
			if (B>A&&C>B) {
				flag = true;
				return flag;
			} else {
				return flag;
			}
		}

		if (flag) {
			return flag;
		}

		flag = calculate (2*A, B, C, K, count+1, flag);
		flag = calculate (A, 2*B, C, K, count+1, flag);
		flag = calculate (A, B, 2*C, K, count+1, flag);

		return flag;
	}
}


Measured memory_bytes: 35664
import sys
import itertools
n,m=map(int,input().split())
ab=[]
for _ in range(m):
    ab.append(list(map(int,input().split())))

lis=list(range(1,n+1))
per_lis =[i for i in list(itertools.permutations(lis)) if i[0]==1]

ans=0

for one_case in per_lis:
    tmp=0
    for j in range(n-1):
        for num in ab:
            if one_case[j]==num[0] and one_case[j+1]==num[1]:
                tmp+=1
            elif one_case[j]==num[1] and one_case[j+1]==num[0]:
                tmp+=1
                    

        if tmp==n-1:
            ans+=1

print(ans)

        




Measured memory_bytes: 8052
from collections import deque
A = deque(list(input()))
B = deque(list(input()))
C = deque(list(input()))

tern = "a"
while True:
  if tern == "a":
    if A:
      tern = A.popleft()
      continue
    win = "A"
    break
  elif tern == "b":
    if B:
      tern = B.popleft()
      continue
    win = "B"
    break
  elif tern == "c":
    if C:
      tern = C.popleft()
      continue
    win = "C"
    break
    
print(win)

Measured memory_bytes: 9316
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(i = 0; i < n; i++)
#define Rep(i, n) for(i = 1; i < n; i++)
#define Ans(s) cout << s << endl;

const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

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

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

typedef long long ll;

// 4,8方向に探索する際に用いる配列
//int dx[4] = { 0,  0, 1, -1 };
//int dy[4] = { 1, -1, 0,  0 };
//int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1 };
//int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1 };

constexpr auto MAX = 100010;

int main()
{
	int ans = inf;
	int n;
	cin >> n;
	vector<int> w(n);
	int i;
	rep(i, n) cin >> w[i];

	vector<int> sums(n + 1);
	for (int i = 1; i <= n; i++)
	{
		sums[i] = w[i - 1] + sums[i - 1];
	}

	for (int i = 0; i < n; i++)
	{
		int a = sums[i] - sums[0];
		int b = sums[n] - sums[i];
		int tmp = abs(a - b);
		ans = min(ans, tmp);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int n,k;
long long ans;
int a[50000006];
int main()
{
    cin>>n>>k;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
	} 
	sort(a+1,a+n+1);
	for(int i=1;i<=n-k;++i) ans+=a[i];
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1024
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    if a[i] % 2==0:
        if a[i] % 3==0 or a[i] % 5==0:
            ans=0
        else:
            ans=1
            break
if ans==0:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 3060
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	long[][][][] a = new long[N+1][4][4][4];
	a[0][3][3][3] = 1;
	long mod = (long)Math.pow(10,9)+7;
	for(int len = 1; len<N+1; len++) {
	    for(int i = 0; i<4; i++) {
		for(int j = 0; j<4; j++) {
		    for(int k = 0; k<4; k++) {
			if(a[len-1][i][j][k] == 0) continue;
			for(int e = 0; e<4;e++) {
			    if(e==2 && i==1 && j==0) continue;
			    if(e==2 && i==0 && j==1) continue;
			    if(e==1 && i==2 && j==0) continue;
			    if(e==2 && i==1 && k==0) continue;
			    if(e==2 && j==1 && k==0) continue;

			    a[len][e][i][j] += a[len-1][i][j][k];
			    if(a[len][e][i][j]>=mod) a[len][e][i][j] %= mod;
			}
		    }
		}
	    }
	}
	long ans = 0;
	for(int i=0; i<4; i++) {
	    for(int j=0; j<4; j++) {
		for(int k=0; k<4; k++) {
		    ans += a[N][i][j][k];
		    ans %= mod;
		}
	    }
	}
	System.out.println(ans);

    }
}

Measured memory_bytes: 21844
#インポート
import sys

#入力用
def ILI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def ISI(): return map(int, sys.stdin.readline().rstrip().split())
def II(): return int(sys.stdin.readline().rstrip())
def ISS(): return sys.stdin.readline().rstrip().split()
def IS(): return sys.stdin.readline().rstrip()

N, M = ISI()
A = [IS() for _ in range(N)]
B = [IS() for _ in range(M)]

def match(x, y):
    ok = True
    for i in range(M):
        for j in range(M):
            if A[x+i][y+j] != B[i][j]:
                ok = False
    return ok


find = False
for i in range(N-M+1):
    for j in range(N-M+1):
        if match(i, j) == True:
            find = True
if find == True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
/**
 * @author torith
 * @date 2018-10-24
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    cin >> N >> M;

    cout << (1900 * M + 100 * (N - M)) * pow(2,M) << "\n";

    return 0;
}



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

using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i < (n); --i)
#define all(x) (x).begin(), (x).end()
#define gsort(x, n) sort((x), (x + n) greater<int>())
#define rv(s) reverse((s).begin(), (s).end())
#define setout(n, x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10);
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).flont_back(a)
#define eb(x, a) (x).emplaes_back(a)
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1e9 + 7;

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

   int a,b,m;
   cin>>a>>b>>m;
   vector<int> a1(a),b1(b);
   int x,y,c;

   int cnt=INF,ans=INF;

   rep(i,0,a) cin>>a1[i],cnt=min(cnt,a1[i]);
   rep(i,0,b) cin>>b1[i],ans=min(ans,b1[i]);
   cnt += ans;

   rep(i,0,m){
      cin>>x>>y>>c;
      ans = a1[x-1] + b1[y-1] - c;
      cnt = min(cnt,ans);
   }

   cout<<cnt<<'\n';
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
	using namespace std;
	typedef long long int ll;
	
	#define pii                 pair<int,int>
	#define vi                  vector<int>
	#define vii                 vector<std::vector<int>> v;
	#define mem(dp,a)           memset(dp,a,sizeof dp)
	#define sonic               ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	#define pb(x)               push_back(x)
	#define mkp(x,y)             make_pair(x,y)
	#define all(c)              c.begin(), c.end()
	#define ff                  first
	#define ss                  second
	#define INF                 INT_MAX
	
	/* Bit Manipulation */
	
	#define isOn(S, j) (S & (1 << j))
	#define setBit(S, j) (S |= (1 << j))
	#define clearBit(S, j) (S &= ~(1 << j)) // to turn off
	#define toggleBit(S, j) (S ^= (1 << j))
	#define lowBit(S) (S & (-S)) // to get lsb
	#define setAll(S, n) (S = (1 << n) - 1)
	
	#define modulo(S, N) ((S) & (N - 1))   // returns S % N, where N is a power of 2
	#define isPowerOfTwo(S) (!(S & (S - 1)))
	#define nearestPowerOfTwo(S) ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))
	#define turnOffLastBit(S) ((S) & (S - 1))
	#define turnOnLastZero(S) ((S) | (S + 1))
	#define turnOffLastConsecutiveBits(S) ((S) & (S + 1))
	#define turnOnLastConsecutiveZeroes(S) ((S) | (S - 1))
	
	void printSet(int vS) {                         // in binary representation
	  printf("S = %2d = ", vS);
	  stack<int> st;
	  while (vS)
	    st.push(vS % 2), vS /= 2;
	  while (!st.empty())                         // to reverse the print order
	    printf("%d", st.top()), st.pop();
	  printf("\n");
	}
		
	/* Bit Manipulation Ends. */
		
	// Global variables declared here...
	
	//*******User-Defined Functions*********//
	
	
	
	//*******Functions end here************//
	
	//*******Main func starts**************//
	int main()
	{
	    sonic;
		int n;
		cin >> n;
		int rem;
		for (int i=1;i<=100000;i++)
		{
			if (n-1000*i <= 0)
			{
				rem = -(n-1000*i);
				break;
			}
		}
		cout << rem << endl;
	}
	//******Main Ends here****************//
	
	
	


Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {

	private static Scanner scan = new Scanner(System.in);

	public static void main(String[] args) {

		int n = scan.nextInt();
		int m = scan.nextInt();

		int count = 0;
		for (int i = 1 ; i < n ; i++) {
			count += i;
		}
		for (int i = 1 ; i < m ; i++) {
			count += i;
		}
		System.out.println(count);

	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<=int(b);++i)
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int INF=numeric_limits<int>::max();
// for(int j=0;j<N;++j) {
int to_int(char c) {
  return c - '0';
}

typedef long long ll;
ll modpow(ll a, ll n, ll MOD) {
  ll res = 1;
  while(n>0){
    if(n&1) res = res * a % MOD;
    a = a * a % MOD;
    n >>= 1;
  }
  return res;
}

int main(void) {
  string S;cin>>S;
  int n = S.length();
  int T[n+10];
  vector<int> M(2020,0);

  T[n] = 0;
  M[T[n]]++;

  for(int i=n-1;i>=0;i--) {
    // pr(to_int(S[n-i-1]));
    T[i] = (T[i+1] + to_int(S[i])*modpow(10,n-i-1,2019)) % 2019;
    M[T[i]]++;
  }

  ll ans=0;

  rep(i,0,2018) {
    int m = M[i];
    ans+=m*(m-1)/2;
  }

  pr(ans);
  return 0;
}


Measured memory_bytes: 4444
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>

const int N = 305, P = 1e9 + 7;

int F[N][N][N];
std::vector< std::pair<int, int> > V[N];

inline void Add(int &x, int y) {
    (x += y) >= P && (x -= P);
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        V[r].push_back(std::make_pair(l, x));
    }
    F[1][0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (std::pair<int, int> p : V[i])
            for (int j = 0; j < i; ++j)
                for (int k = 0; k <= std::max(0, j - 1); ++k) {
                    if (p.second == 1 && j >= p.first) F[i][j][k] = 0;
                    if (p.second == 2 && (j < p.first || k >= p.first)) F[i][j][k] = 0;
                    if (p.second == 3 && k < p.first) F[i][j][k] = 0;   
                }
        for (int j = 0; j < i; ++j)
            for (int k = 0; k <= std::max(0, j - 1); ++k) {
                Add(F[i + 1][j][k], F[i][j][k]);
                Add(F[i + 1][i][j], F[i][j][k]);
                Add(F[i + 1][i][k], F[i][j][k]);
            }
    }
    int Ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= std::max(0, i - 1); ++j) Add(Ans, F[n][i][j]);
    Ans = 3LL * Ans % P;
    printf("%d\n", Ans);
    return 0;
}

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

int main(void)
{
    int H,W,ans = 0,cnt = 0;
    cin >> H >> W;
    string s[H];

    vector<vector<char>> S(H, vector<char>(W));

    rep(i, H){
        cin >> s[i];
    }

    rep(i,H){
        rep(j,W){
            if(s[i][j] == '.'){
                cnt = 0;
                for(int a = i-1;a <= i+1;a++){
                    for(int b = j-1;b <= j+1;b++){
                        if(a >= 0 && a < H && b >= 0 && b < W && s[a][b] == '#')
                            cnt++;
                    }
                }
                char c = '0' + cnt;
                s[i][j] = c;
            }
        }
    }

    rep(i,H){
        cout << s[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 3588
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;

template<class _T> static void getint(_T& a) {
	std::cin >> a;
}
template<class _T> static void getint(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void getint(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}

static void ARC081C();

int main()
{
	ARC081C();
	fflush(stdout);
	return 0;
}

static void ARC081C()
{
	int N;
	getint(N);

	std::vector<LLONG> ai(N, 0);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &ai[i]);
	}

	std::sort(ai.begin(), ai.end(), std::greater<LLONG>());

	LLONG e1 = 0, e2 = 0;
	LLONG now, bfr = 0;
	for (int i = 0; i < N; i++) {
		now = ai[i];
		if (now == bfr) {
			if (!e1) {
				e1 = now;
			}
			else {
				e2 = now;
				break;
			}
			now = 0;
		}
		bfr = now;
	}
	printf("%lld\n", e1 * e2);
}


Measured memory_bytes: 1024
from decimal import *

input()
N = list(map(int, input().split()))
N.sort()
ans = 0
while True:
    try:
        tmpa = N.pop(0)
        ans = tmpa
        tmpb = N.pop(0)
        N.append((Decimal(tmpa)+Decimal(tmpb))/Decimal(2))
        N.sort()
    except IndexError:
        break
print(ans)

Measured memory_bytes: 5076
N = int(input())

xyz = [map(int, input().split()) for i in range(N)]
t, x, y = [list(i) for i in zip(*xyz)]



if N == 1:
    T = N
    SUM = abs(x[0] + y[0])
    if T < SUM:
        print('No')
        exit()
    elif (T % 2 == 0 and SUM % 2 != 0) or (T % 2 != 0 and SUM % 2 == 0):
        print('No')
        exit()
    else:
        print('Yes')
        exit()
    

for i in range(N-1):
    T = t[i+1] - t[i]
    X = x[i+1] - x[i]
    Y = y[i+1] - y[i]
    

    
    
    if t[0] < abs(x[0] + y[0]):
        print('No')
        exit()
    elif (t[0] % 2 == 0 and abs((x[0] + y[0])) % 2 != 0) or (t[0] % 2 != 0 and abs((x[0] + y[0])) % 2 == 0):
        print('No')
        exit()
    

    SUM = abs(X + Y)

    if T < SUM:
        print('No')
        exit()
    elif (T % 2 == 0 and SUM % 2 != 0) or (T % 2 != 0 and SUM % 2 == 0):
        print('No')
        exit()
    else:
        continue
    
print('Yes')

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

int main() {
    int n, combi = 0;
    scanf("%d", &n);
    vector<double> values(n);

    rep(i, n) {
        cin >> values.at(i);
    }

    sort(values.begin(), values.end());
    double sum = (values.at(0) + values.at(1))/2;
    if (n == 2)
    {
        /* code */
        cout << sum << endl;
        return 0;
    }
    

    int i = 2;
    for (i; i < n; i++) {
        sum = (values.at(i) + sum)/2;
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 256
n,m=gets.split.map(&:to_i)
a=Array.new
n.times do
    a.push(gets.split.map(&:to_i))
end
b=Array.new
m.times do
    b.push(gets.to_i)
end
for i in 0...n
    c=0
    for j in 0...m
        c+=a[i][j]*b[j]
    end
    p c
end


Measured memory_bytes: 6984
import Control.Applicative
import Control.Monad

data BTree = BEmpty | BNode BTree BTree deriving Eq
instance Show BTree where
  show BEmpty = ""
  show (BNode l r) = '(' : show l ++ ',' : show r ++ ")"

parse :: String -> BTree
parse ss = let (t,_) = psub ss in t
  where
    psub ('(':s1) = let (left, (',':s2)) = psub s1 in let (right, (')':s3)) = psub s2 in (BNode left right, s3)
    psub s = (BEmpty, s)

btintersection :: BTree -> BTree -> BTree
btintersection BEmpty _ = BEmpty
btintersection _ BEmpty = BEmpty
btintersection (BNode l1 r1) (BNode l2 r2) = BNode (btintersection l1 l2) (btintersection r1 r2)

btunion :: BTree -> BTree -> BTree
btunion BEmpty r = r
btunion l BEmpty = l
btunion (BNode l1 r1) (BNode l2 r2) = BNode (btunion l1 l2) (btunion r1 r2)

solve ["i", lt, rt] = btintersection (parse lt) (parse rt)
solve ["u", lt, rt] = btunion (parse lt) (parse rt)

main = map (solve . words) . lines <$> getContents >>= mapM_ print


Measured memory_bytes: 3988
from collections import Counter
N=int(input())
s=[]
for i in range(N):
    s.append(input())
M=int(input())
t=[]
for i in range(M):
    t.append(input())

sc=Counter(s).most_common()
li=[]
for k,j in sc:
    cnt=0
    for x in range(len(t)):
        if(k==t[x]):
            cnt+=1
    li.append(j-cnt)
if(len(li)!=0):
    print(max(0,max(li)))

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

int main(){
    int N;  cin >> N;
    vector<ll> A(N);
    for(int i=0; i<N; i++)
        cin >> A[i];
    sort(A.begin(), A.end(), greater<ll>());
    
    int n = N/2;
    if(N%2==0){
        ll ans = 0;
        for(int i=0; i<n; i++) ans += 2*A[i];
        for(int i=n; i<N; i++) ans -= 2*A[i];
        ans -= A[n-1];
        ans += A[n];
        cout << ans << endl;
    }else{
        int n = N/2;
        ll sum1 = 0;
        for(int i=0; i<n-1; i++) sum1 += 2*A[i];
        for(int i=n+1; i<N; i++) sum1 -= 2*A[i];
        sum1 += A[n] + A[n-1];

        ll sum2 = 0;
        for(int i=0; i<n; i++) sum2 += 2*A[i];
        for(int i=n+2; i<N; i++) sum2 -= 2*A[i];
        sum2 -= A[n] + A[n+1];
        cout << max(sum1, sum2) << endl;
    }
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    int res = 0;
    int i = 0;
    while (i < n) {
        int c = upper_bound(a, a + n, a[i]) - lower_bound(a, a + n, a[i]);
        res += c < a[i] ? c : c - a[i];
        i += c;
    }
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 640