akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
 
int n, m, a, b, s1, s2, ans=INF, temp[1500], col[705], f[705];
bool mmp[705][705], vis[1005];
 
void dfs(int x, int color)
{
	if(vis[x])
	{
		if(col[x]!=color) {printf("-1\n"); exit(0);}
		return;
	}
	vis[x]=1; col[x]=color;
	if(color==1) s1++;
	else s2++;
	for(int i=1; i<=n; i++)
	{
		if(mmp[x][i]==0) continue;
		dfs(i, 3-color);
	}
}
 
int main()
{
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++)
	{
		scanf("%d%d", &a, &b);
		mmp[a][b]=mmp[b][a]=1;	
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			if(i==j) mmp[i][j]=0;
			else mmp[i][j]^=1;
		}
	}
	f[0]=1;
	for(int i=1; i<=n; i++)
	{
		if(vis[i]) continue;
		s1=s2=0;
		dfs(i, 2);
		for(int i=0; i<=n; i++)
		{
			temp[i+s1]|=f[i];
			temp[i+s2]|=f[i];
		}
		for(int i=0; i<=n; i++)
		{
			f[i]=temp[i];
			temp[i]=0;
		}
	}
	for(int i=0; i<=n; i++) 
		if(f[i]) ans=min(ans, i*(i-1)/2+(n-i)*(n-i-1)/2);
	printf("%d\n", ans);
} 

Measured memory_bytes: 768
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int main(){
  vector<int>ve;
  int dp[301] = {0};
  for(int i = 1 ; i*i <= 300 ; i++ )ve.push_back(i*i);

  dp[0] = 1;
  for(int j = 0 ; j < ve.size() ; j++ ){
    for(int i = ve[j] ; i <= 300 ; i++  ){
      dp[i] += dp[i - ve[j]];
    }
  }
  int n;
  while(cin >> n,n){
    cout << dp[n] << endl;
  }
  return 0;
}

Measured memory_bytes: 1216
import sys
sys.setrecursionlimit(10**6)

n=int(input())
a=list(map(int,input().split()))

for i in range(n):
    if a[i]==0:
        print(0)
        exit()

ans=1
for i in range(n):
#    print(ans)
    if ans>10**18:
        print(-1)
        exit()
    else:
        ans*=a[i]

if ans>10**18:
    print(-1)
else:
    print(ans)



Measured memory_bytes: 21664
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		sc.close();
		int x500 = 0, x5 = 0;
		x500 = X / 500;
		X = X % 500;
		x5 = X / 5;
		System.out.println(x500 * 1000 + x5 * 5);
	}
}


Measured memory_bytes: 21844
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
struct Node {
	int key;
	Node *l, *r, *p;
};
Node *root, *NIL; 
inline void pre(Node *u) {

	cout << " " << u->key;
	if (u->l != NIL) pre(u->l);
	if (u->r != NIL) pre(u->r);
}
inline void in(Node* u) {
	if(u->l != NIL)in(u->l);
	cout << " " << u->key;
	if (u->r != NIL) in(u->r);

}
inline int find(int k) {
	Node *r = root;
	//Node *f = NIL;
	Node *f;
	f = (Node *)malloc(sizeof(Node));
	f->key = k;
	while (r != NIL) {
		if (k < r->key)
			r = r->l;
		else if(k > r->key) r = r->r;
		else return 1;
	}
	return 0;
}
inline void insert(int k) {
	Node *x = root;
	Node *y = NIL;
	Node *z;
	int cnt = 0;
	z = (Node *)malloc(sizeof(Node));
	z->key = k;
	z->l = NIL;
	z->r = NIL;
	while (x != NIL) {
		y = x;
		if (x->key > z->key)
			x = x->l;
		else
			x = x->r;
	}
	z->p = y;
	if (y == NIL) {
		root = z;
	}
	else if (y->key > z->key) {
		y->l = z;
	}
	else if (y->key < z->key) {
		y->r = z;
	}
}
int main(){
	int m;
	cin >> m;
	string com;
	int n;
	for (int i = 0; i < m; i++) {
		cin >> com;
		if (com == "insert") {
			scanf("%d", &n);
			insert(n);
		}
		else if(com == "print"){
			in(root);
			cout << endl;
			pre(root);
			cout << endl;
		}
		else {
			scanf("%d", &n);
			if (find(n)) cout << "yes" << endl;
			else cout << "no" << endl;
		}

	}
	return 0;
}

Measured memory_bytes: 26644
N, M = map(int, input().split())

if abs(N-M)>=2:
    print(0)
    exit(0)

def kaijo(p):
    a = 1
    while p > 0:
        a *= p
        a %= 10**9+7
        p -= 1
    return a

if N == M:
    print((kaijo(N)*kaijo(M)*2)%(10**9+7))
else:
    print((kaijo(N)*kaijo(M))%(10**9+7))

Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args){
		BufferedReader insBR = new BufferedReader(new InputStreamReader(System.in));
		try{

			//最初の行の数値を読み取る。
			String[] strLine = insBR.readLine().split(" ");
			int[] intLine = new int[strLine.length];
			for(int i = 0; i < strLine.length; i++){
				intLine[i] = Integer.parseInt(strLine[i]);
			}

			//次の行以降を読み取る際の配列を用意。
			int intR = intLine[0];
			int intC = intLine[1];
			int[][] intRC = new int[intR][intC];
			String[][] strRC = new String[intR][intC];

			//数値を読み取り、配列につめる。
			for(int i = 0; i < intR; i++){
				strRC[i] = insBR.readLine().split(" ");
			}
			for(int i = 0; i < intR; i++){
				for(int j = 0; j < intC; j++){
					intRC[i][j] = Integer.parseInt(strRC[i][j]);
				}
			}

			//出力用の配列を用意。
			int[][] intPrint = new int[intR + 1][intC + 1];

			//1行ごとに合計値を算出。
			for(int i = 0; i < intR; i++){
				for(int j = 0; j < intC; j++){
					intPrint[i][j] = intRC[i][j];
					intPrint[i][intC] += intPrint[i][j];
					intPrint[intR][intC] += intPrint[i][j];
				}
			}

			//1列ごとに合計値を算出。
			for(int i = 0; i < intC; i++){
				for(int j = 0; j < intR; j++){
					intPrint[intR][i] += intPrint[j][i];

				}
			}

			//出力
			for(int i = 0; i < intPrint.length; i++){
				for(int j = 0; j <= intC; j++){
					if(j != intC){
						System.out.print(intPrint[i][j] + " ");
					}else{
						System.out.println(intPrint[i][j]);
					}
				}
			}




		}catch(IOException e){
			e.printStackTrace();
		}catch(NumberFormatException e){
			e.printStackTrace();
		}
	}
}



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

using namespace std;

typedef long long ll;

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

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

bool solve(const string &S) {
    int slen = (int) S.size();
    for (int i = 0; i <= slen; i++) {
        for (int j = i; j <= slen; j++) {
            string s = S.substr(0, i);
            if (j != slen) {
                s += S.substr(j + 1, slen - j - 1);
            }
            // cout << s << endl;
            if (s == "keyence") {
                return true;
            }
        }
    }
    return false;
}

int main(void) {
    string S;
    cin >> S;

    if (solve(S)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}


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

ll solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> A[i];
    }
    ll dp[N][N];
    for ( int h = 0; h < N; h++ ) {
        ll sg = (N-h) % 2 == 1 ? 1 : -1;
        for ( int i = 0; i + h < N; i++ ) {
            ll xy = 0;
            if ( h == 0 ) {
                xy = sg * A[i];
            } else {
                ll t1 = dp[i+1][i+h] + sg * A[i];
                ll t2 = dp[i][i+h-1] + sg * A[i+h];
                if ( ( t1 - t2 ) * sg >= 0 ) xy = t1;
                else xy = t2;
            }
            dp[i][i+h] = xy;
        }
    }
    return dp[0][N-1];
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 70400
#include <iostream>
#include <algorithm>
using namespace std;
int v[100004];
int cmmdc(int a,int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    int n,k,i,c;
    cin>>n>>k;
    cin>>v[1];
    c=v[1];
    for(i=2;i<=n;i++)
    {
        cin>>v[i];
        c=cmmdc(c,v[i]);
    }
    sort(v+1,v+n+1);
    if(k>v[n])
    {
        cout<<"IMPOSSIBLE";
        return 0;
    }
    for(i=n;v[i]>=k&&i>=1;i--)
    {
     if((v[i]-k)%c==0)
     {
      cout<<"POSSIBLE";
      return 0;
     }
    }
    cout<<"IMPOSSIBLE";
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,l;
cin >> n >> l;
    vector<string> vec(n);
    for(int i=0; i < n; i++){
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());
    string ret = "";
    for_each(vec.begin(), vec.end(), [&ret](string s){
        ret += s;
    });

    cout << ret << endl;
    return 0;
}

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

typedef long long ll;

int main(){
	int N,K;
	cin >> N >> K;
	vector<int> H(N);
	rep(i,N){ cin >> H[i]; }
	sort(H.begin(),H.end());
	reverse(H.begin(),H.end());
	if(N<=K){cout << 0 << endl; return 0;}
	ll ans = accumulate(H.begin()+K, H.end(), 0LL);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL


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

    int N;
    cin >> N;

    vs32 A(N + 2, 0);
    int s = 0;
    rep (i, N)
    {
        cin >> A[i + 1];
        s += abs(A[i + 1] - A[i]);
    }
    s += abs(A[N]);

    int l, r;
    int m;
    rep (i, N)
    {
        m = i + 1;
        l = MIN(A[m - 1], A[m + 1]);
        r = MAX(A[m - 1], A[m + 1]);
        if (A[m] >= l && A[m] <= r)
        {
            cout << s << "\n";
        }
        else if (A[m] < l)
        {
            cout << s - 2 * abs(A[m] - l) << "\n";
        }
        else
        {
            cout << s - 2 * abs(A[m] - r) << "\n";
        }
    }

    return 0;
}



Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  cin >>a>>b;
  
  if(a>b){
    for(int i=0; i<a; i++){
      cout<<b;
      }
    }
  
  else{
    for(int i=0; i<b; i++){
      cout<<a;
      }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  string s;
  R s;
  rep(i,s.size()) {
    if(s[i]=='1') s[i]='9';
    else if(s[i]=='9') s[i]='1';
  }
  pr(s);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
  unsigned long n,a,b,c,d;
  scanf("%lu%lu%lu",&n,&a,&b);
  c=n/(a+b);
  d=n%(a+b);
  if(d<a){
    cout<<(c*a)+d<<endl;
  }else{
    cout<<(c+1)*a<<endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pi acos(-1)
#define mod 1000000007
#define inf INT_MAX
int main()
{
    ll i,j,k,n,t,ans=0;
    cin>>n;
    j=n;
    for(i=1;i<=3;i++)
    {
        ans+=j;
        j*=n;
    }
    cout<<ans<<endl;







}




Measured memory_bytes: 3620
n, m = map(int, input().split())
 
max_left = 1
min_right = n
 
for i in range(m):
    left, right = map(int, input().split())
    max_left = max(max_left, left)
    min_right = min(min_right, right)
 
print(max(min_right - max_left + 1, 0))

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

vector<int> graph[100005];

int getgrundy(int t, int p)
{
    int ret = 0;
    for (int nxt : graph[t])
    {
        if (nxt == p) continue;
        ret ^= getgrundy(nxt, t) + 1;
    }
    return ret;
}

int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    if (getgrundy(1, -1)) printf("Alice\n");
    else printf("Bob\n");
}


Measured memory_bytes: 10368
#include<iostream>
#include<string>

int main(){
        std::string S, T;
        std::cin >> S >> T;
        int count = 0;
        int _min = T.size();
        int _limit = S.size() - T.size();
        for (int i = 0; i < _limit+1; i++) {
            count = 0;
            std::string R = S.substr(i, T.size());
            for (int j = 0; j < T.size(); j++) {
                if (R[j] != T[j]) {
                    count += 1;
                }
            }
            if (count < _min) {
                _min = count;
            }
        }
        std::cout << _min << std::endl;
    return 0;
}

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

//type
#define ll long long
typedef pair<int, int> P;
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素
#define Z class
// OTHER
// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) { return x * x; }
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
// loop
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= ll(b); i--)
#define FORA(i, I) for (const auto &i : I)

// vector
#define ALL(x) x.begin(), x.end()

// output
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n", (x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define ln cout << '\n'
template <Z A>
void pr(A a)
{
  cout << a;
  ln;
}
template <Z A, Z B>
void pr(A a, B b)
{
  cout << a << ' ';
}

int ans = 0;
bool check = 0;
string s;
int N = 3;
vector<int> v(N);
int a, b;
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

int main()
{
  int c;

  cin >> a;
  pr((24 - a) + 24);
  return 0;
}

Measured memory_bytes: 3596
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.regex.Pattern;
import java.util.stream.Stream;

public class Main {
  public static void main(String[] args) {

    new Main().run();
  }

  public void run() {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      String line = br.readLine();
      final Pattern delim = Pattern.compile("\\s");
      int[] arrayS = delim
        .splitAsStream(line)
        .mapToInt(Integer::parseInt)
        .toArray();

      OptionalInt max =
        Arrays.stream(arrayS).max();

      dispIntArray( countingSort(arrayS, max.getAsInt()) );
    }
    catch ( IOException e ) {
      System.out.println("IOException!");
    }

  }

  public int[] countingSort(int[] a, int k) {

    int   aLength = a.length;
    int[] result  = new int[aLength];
    int[] counter = new int[k+1];

    for (int var : a) {
      counter[var]++;
    }

    for (int i=1, max=k+1; i < max; i++) {
      counter[i] += counter[i-1];
    }

    for (int i=aLength-1, val=0; i>=0; i--) {
      val = a[i];
      result[counter[val]-1] = val;
      counter[val]--;
    }

    return result;
  }

  public void dispIntArray(int[] target) {
    StringBuilder s = new StringBuilder();

    for (int i : target) { s.append(i).append(" "); }
    s.setLength(s.length()-1);

    System.out.println(s);
  }
}


Measured memory_bytes: 184396
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int, int >
#define F first
#define S second
#define int  long long int
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;

const int N=5005 ;

bitset <N> dp,pd;
ll a[N];
int32_t main(){
    ll n,k;
    cin >> n >> k;
    for (int i=1;i<=n;i++){
        cin >> a[i];
    }
    ll l=0,r=n+1;
    sort(a+1,a+n+1);
    while(r-l>1){
        ll mid=(r+l)/2;
        if (a[mid]>=k){
            r=mid;
            continue;
        }
        dp=pd;
        dp[0]=1;
        for (int i=1;i<=n;i++){

            if (i==mid || a[i]>=k){
                continue;
            }
            dp |= (dp << a[i]);
        }
        //for (int i=1;i<=k;i++){
          //  cout << mid << " " << i << " " << dp[i] << endl;
        //}
        bool p1=0;
        for (int i=k-1;i>=k-a[mid];i--){
            p1=max((ll)p1,(ll)dp[i]);
        }
       // cout << p1 << endl;
        if (p1){
            r=mid;
        }
        else{
            l=mid;
        }

    }
    cout << l;
}


























Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int a,b;
  int sum;
  int i;

  while(scanf("%d%d",&a,&b)!=EOF){
    sum=a+b;
    for(i=0;sum>0;i++){
      sum /= 10;
    }
    printf("%d\n",i);
  }
  return 0;
}

Measured memory_bytes: 600
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  int N,A;
  cin >> N >> A;
  N %= 500;
  if(N <= A) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

/** 組み合わせテーブル計算

    O(n^2)

    ret[n][r]: nCr
*/
std::vector<std::vector<int64_t>>
comb(int n) {
    std::vector<std::vector<int64_t>> v(n + 1, std::vector<int64_t>(n + 1, 0));
    for (size_t i = 0; i < v.size(); i++) {
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for (size_t j = 1; j < v.size(); j++) {
        for (size_t k = 1; k < j; k++) {
            v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
        }
    }
    return v;
}


int main()
{
    int64_t N, A, B;
    std::cin >> N >> A >> B;

    std::vector<int64_t> V;
    for (decltype(N) i = 0; i < N; ++i) {
        int64_t t;
        std::cin >> t;
        V.push_back(t);
    }

    // 降順ソート
    std::sort(std::begin(V), std::end(V),
              [](const auto& a, const auto& b) {
                  return a > b;
              });

    auto last_entry_count = std::count(std::begin(V), std::end(V), V[A-1]);
    auto last_entry_count_in_A = std::count(std::begin(V), std::begin(V)+A, V[A-1]);

    cout.precision(20);
    std::cout << std::accumulate(V.begin(), V.begin() + A, 0LL) / (double)A << std::endl;

    int64_t ans = 0;
    if (V[0] == V[A-1]) {
        auto cc = comb(last_entry_count);
        for (int64_t i = A; i <= std::min(last_entry_count, B); ++i) {
            ans += cc[last_entry_count][i];
        }
    }
    else {
        auto cc = comb(last_entry_count);
        ans = cc[last_entry_count][last_entry_count_in_A];
    }

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


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

using namespace std;

ll n;
ll sum;
int main()
{
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        if (i % 3 != 0 && i % 5 != 0)
        {
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3652
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int[] numbers = new int[1000001];
    	for(int i=0;i<=1000000;i++) {
    		numbers[i] = 0;
    	}
    	numbers[0] = 1;
    	numbers[1] = 1;
    	for(int i=2;i<=1000000/2;i++) {
    		for(int j=2;j<=1000000/i;j++) {
    			numbers[i*j] = 1;
    		}
    	}
    	while(true) {
    		int a = sc.nextInt();
    		int d = sc.nextInt();
    		int n = sc.nextInt();
    		if(a+d+n==0) break;
    		int count = 0;
    		loop:for(int i=a;;i+=d) {
    			if(numbers[i] == 0) count++;
    			if(count == n) {
    				System.out.println(i);
    				break loop;
    			}
    		}
    	}
    }
}



Measured memory_bytes: 33308
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


def Find(x):    #xの根を返す
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    #親の更新(根を直接親にして参照距離を短く)
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    #xとyを繋げる
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

N,M = inpl()

table = [i for i in range(N)]    #木の親 table[x] == x なら根
rank  = [1 for i in range(N)]    #木の長さ
size  = [1 for i in range(N)]

ABs = [inpl() for i in range(M)]
ans = N*(N-1)//2
ans_list = [ans]

for A,B in reversed(ABs):
    A -= 1
    B -= 1
    #print(A,B,Size(A),Size(B))
    if not Check(A,B):
        ans -= Size(A) * Size(B)
        Unite(A,B)
    ans_list.append(ans)

for i in reversed(range(M)):
    print(ans_list[i])


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

int main() {
  int n;
  cin >> n;
  if(n % 1000 == 0) {
    cout << 0 << endl;
  } else {
    cout << 1000 - n % 1000 << endl;
  }
  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;

stack<int> S;


int main()
{
    char c;
    while(true)
    {
        c=getchar();
        if(c=='+')
        {
            int a=S.top();
            S.pop();
            int b=S.top();
            S.pop();
            S.push(a+b);
        }
        else if(c=='-')
        {
            int a=S.top();
            S.pop();
            int b=S.top();
            S.pop();
            S.push(b-a);
        }
        else if(c=='*')
        {
            int a=S.top();
            S.pop();
            int b=S.top();
            S.pop();
            S.push(a*b);
        }
        else
        {
            ungetc(c,stdin);
            int a;
            scanf("%d",&a);
            S.push(a);
        }
        c=getchar();
        if(c=='\n')
        {
            break;
        }
    }
    int a;
    a=S.top();
    printf("%d\n",a);
    return 0;
}



Measured memory_bytes: 3236
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
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; }

void solve() {
    int h,w;
    cin >> h >> w;
    int a,b;
    set<PII> s;
    multiset<int> m;
    REP(i,0,w) s.emplace(i,i);
    REP(i,0,w) m.insert(0);
    s.emplace(1<<30,1<<30);
    m.insert(1<<30);
    REP(i,0,h) {
        // dump("---");
        cin >> a >> b;
        --a;
        --b;
        // dump("dump");
        auto it = s.lower_bound(MP(a,0));
        auto bt = it;
        // dump("dump");
        int lv = -1;
        while (it != s.end() && it->first <= b) {
            // dump(it->first);
            chmax(lv, it->second);
            int diff = it->first - it->second;
            // dump((diff));
            m.erase(m.lower_bound(diff));
            ++it;
        }
        // dump("dump");
        // if (bt != s.end()) {
        //     dump(bt->first);
        //     dump(bt->second);
        // }

        if (it != bt) {
            // --it;
            s.erase(bt, it);
        }
        // dump(a);
        // dump(b);
        // dump(lv);
        if (lv > -1 && b + 1 < w && s.lower_bound(MP(b+1,0))->first != b+1) {
            // dump(lv);
            s.emplace(b+1,lv);
            m.insert(b+1-lv);
        }
        // dump("dump");
        // dump(*m.begin());
        if ((*m.begin()) == 1<<30) cout << -1 << endl;
        else cout << (*m.begin()) + i + 1 << endl;
        // for (auto &sv: s) dump(sv.first);
        // for (auto &v: m) dump(v);
    }
}

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

Measured memory_bytes: 22344
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(;;){
        int n;
        cin>>n;
        if(!n) return 0;
        vector<int> a(n);
        rep(i,0,n) cin>>a[i];
        sor(a);
        int ans=1e8;
        rep(i,1,n) ans=min(ans, a[i]-a[i-1]);
        cout <<ans<<"\n";
    }
}


Measured memory_bytes: 3220
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        while (m-- > 0) {
            n -= sc.nextInt();
        }
        if (n < 0) {
            System.out.println(-1);
        } else {
            System.out.println(n);
        }
    }
}


Measured memory_bytes: 46320
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

void push(int);

int pop(void);

int top,kan[1000];

int main()
{
  int x,y,top=0;
  char s[100];

  while(scanf("%s",s)!=EOF)
    {
      if(s[0]=='+')
	{
	  x=pop();
	  y=pop();
	  push(x+y);
	}
      else if(s[0]=='-')
	{
	  y=pop();
	  x=pop();
	  push(x-y);
	}
      else if(s[0]=='*')
	{
	  x=pop();
	  y=pop();
	  push(x*y);
	}
      else
	{
	  push(atoi(s));
	}
    }
  printf("%d\n",pop());
  return 0;
}

void push(int a)
{  
  kan[++top]=a;
}

int pop()
{
  top--;
  return kan[top+1];
}




Measured memory_bytes: 2108
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    int x;
    cin>>x;
    if (x == 3 || x == 5 || x == 7) cout<<"YES";
    else cout<<"NO";

    return 0;
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

struct UnionFind
{
    int i;
    vector<int> par;
    vector<int> size;
    UnionFind(int n): par(n),size(n,1){
        for(i = 0;i < n;++i){
            par.at(i) = i;
        }
    }
    
    int root(int x){
        if(par.at(x) == x){
            return x;
        }else{
            return par.at(x) = root(par.at(x));
        }
    }
    
    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry){
            return;
        }else{
            if(size.at(rx) < size.at(ry)){
                swap(rx,ry);
            }
            par.at(ry) = rx;
            size.at(rx) += size.at(ry);
            return;
        }
    }
    
    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    
    int get_size(int x){
        return size.at(root(x));
    }
};

int main()
{
    ll i,j;
    ll n,m;
    cin >> n >> m;
    
    vector<vector<ll>> ling(m);
    for(i = 0;i < n;++i){
        ll k;
        cin >> k;
        rep(j,k){
            ll l;
            cin >> l;
            --l;
            ling.at(l).push_back(i);
        }
    }

    UnionFind uf(n);

    for(i = 0;i < m;++i){
        for(j = 1;j < ling.at(i).size();++j){
            uf.unite(ling.at(i).at(0), ling.at(i).at(j));
        }
    }

    if(uf.get_size(0) == n){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 4736
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<deque>
#include<map>
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    map<int, int> s;

    // n > 0
    auto prime_factorize = [&](ll n) -> void {
        // i > 1
        for (int i = 2; i*i <= n; i++) {
            if (n%i != 0) continue;
            int num = 0;
            while (n%i == 0) {
                num++;
                n /= i;
            }
            s[i] += num;
        }
        if (n != 1) s[n] += 1;
    };

    for (int i = 2; i <= n; i++) {
        prime_factorize(i);
    }
    
    auto rec = [&](auto &&rec, auto p, int mul) -> int {
        if (p == s.end()) {
            // この経路で来た場合は成功
            if (mul == 1) return 1;
            // それ以外は失敗
            return 0;
        }

        int res = 0;
        for (int i = 0; i <= p->second; i++) {
            if (mul%(i+1) != 0) continue;
            res += rec(rec, ++p, mul/(i+1));
            p--;
        }
        return res;
    };

    cout << rec(rec, s.begin(), 75) << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    F=list(map(int,input().split()))
    F.sort(reverse=True)
    A.sort()
    right=10**12
    left=-1
    while right-left>1:#区間(left,right]に解Xがある
        x=(right+left)//2
        k_sum=0
        for i in range(n):
            k_sum+=max(0,A[i]-x//F[i])
        if k_sum<=k:
            right=x
        else:
            left=x
    print(right)
    

if __name__=='__main__':
    main()

Measured memory_bytes: 113152
#include <bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    ll ret=0,flag=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9')ret=ret*10+(c^'0'),c=getchar();
    return flag*ret;
}

ll h;

int main()
{
    h=read();
    ll ans=0,num=1;
    while(h)
    {
        ans+=num;
        h>>=1,num<<=1;
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 256
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;
import std.ascii;


void main()
{
  auto s = readln.chomp.array;
  
  if (s.length == 3) {
    s.reverse();
  }
  s.writeln;
}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> p(n), c(n);
  rep(i,n) cin >> p[i];
  rep(i,n) cin >> c[i];
  rep(i,n) --p[i];

  ll ans = -1e18;
  rep(s,n) {
    int x = s;
    ll total = 0;
    vector<int> v;
    while (1) {
      x = p[x];
      v.push_back(c[x]);
      total += c[x];
      if (x == s) break;
    }
    int l = v.size();
    ll t = 0;
    rep(i,l) {
      t += v[i];
      if (i+1 > k) break;
      ll now = t;
      if (total > 0) {
        now += total * ((k-1-i)/l);
      }
      ans = max(ans, now);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3688
n,k = map(int,input().split())
r,s,p = map(int,input().split())
T = input()

#dp[i][j]:i回目にjを出した時のそれまでの合計点の最大値。j:0グー1チョキ2パー
dp = [[0 for j in range(3)] for i in range(n)]
for i in range(0,k):
    if T[i] == 'r':
        dp[i][2] = p 
    elif T[i] == 's':
        dp[i][0] = r 
    else:
        dp[i][1] = s 
    for j in range(k,n-i,k):
        if T[i+j] == 'r':
            dp[i+j][2] = max(dp[i+j-k][0]+p,dp[i+j-k][1]+p)
            dp[i+j][1] = max(dp[i+j-k][0],dp[i+j-k][2])
            dp[i+j][0] = max(dp[i+j-k][1],dp[i+j-k][2])
        elif T[i+j] == 's':
            dp[i+j][0] = max(dp[i+j-k][1]+r,dp[i+j-k][2]+r)
            dp[i+j][1] = max(dp[i+j-k][0],dp[i+j-k][2])
            dp[i+j][2] = max(dp[i+j-k][0],dp[i+j-k][1])
        else:
            dp[i+j][1] = max(dp[i+j-k][2]+s,dp[i+j-k][0]+s)
            dp[i+j][0] = max(dp[i+j-k][1],dp[i+j-k][2])
            dp[i+j][2] = max(dp[i+j-k][0],dp[i+j-k][1])
    
total = 0
#print(dp)
for i in range(n-1,max(0,n-1-k),-1):
    total += max(dp[i])
print(total)
        
    



Measured memory_bytes: 22408
n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

d = {0 : 1}
s = 0
r = 0
for i in range(n):
    s += a[i]
    s %= m
    r += d[s] if s in d else 0
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

print(r)


Measured memory_bytes: 14252
def main():
    n = int(input())
    a = list(map(int,input().split()))
    s = 1
    if 0 in a:
        print(0)
        return
    for i in range(n):
        s *= a[i]
        if s>10**18:
            print(-1)
            return
    print(s)

if __name__ == "__main__":
    main()


Measured memory_bytes: 21788
#include <bits/stdc++.h>
using namespace std;
struct Update {
    int a1;
    int a2;
    int val;
    Update(int a, int b, int c) : a1(a), a2(b), val(c) {};
};
int main() {
    int n, ttt;
    cin >> n;
    vector<int> a;
    for (int i = 0; i < 3 * n; i++) {
        cin >> ttt;
        a.push_back(ttt - 1);
    }
    int res = 0;
    if (n == 1) {
        res = (a[0] == a[1]) && (a[1] == a[2]);
        cout << res;
        return 0;
    }
    vector<vector<int>> point(n, vector<int>(n, -12800));
    vector<Update> up;
    vector<int> maxWhenX(n, -64800);
    //Initialize
    point[a[0]][a[1]] = 0;
    point[a[1]][a[0]] = 0;
    maxWhenX[a[0]] = 0;
    maxWhenX[a[1]] = 0;
    vector<int> te;
    int m = 0;
    for (int i = 1; i < n; i++) {
        te.clear();
        te.push_back(a[3 * i - 1]);
        te.push_back(a[3 * i]);
        te.push_back(a[3 * i + 1]);
        if (te[0] == te[1] && te[1] == te[2]) {
            res++;
            continue;
        }
        up.clear();
        up.push_back(Update(te[0], te[1], m));
        up.push_back(Update(te[0], te[2], m));
        up.push_back(Update(te[1], te[2], m));
        up.push_back(Update(te[0], te[1], point[te[2]][te[2]] + 1));
        up.push_back(Update(te[2], te[1], point[te[0]][te[0]] + 1));
        up.push_back(Update(te[0], te[2], point[te[1]][te[1]] + 1));
        for (int j = 0; j < n; j++) {
            up.push_back(Update(te[0], j, maxWhenX[j]));
            up.push_back(Update(te[1], j, maxWhenX[j]));
            up.push_back(Update(te[2], j, maxWhenX[j]));
            if (te[0] == te[1]) up.push_back(Update(te[2], j, point[te[0]][j] + 1));
            else if (te[2] == te[1]) up.push_back(Update(te[0], j, point[te[1]][j] + 1));
            else if (te[0] == te[2]) up.push_back(Update(te[1], j, point[te[2]][j] + 1));
        }
        for (auto u : up) {
            point[u.a1][u.a2] = point[u.a2][u.a1] = max(point[u.a1][u.a2], u.val);
            m = max(u.val, m);
            maxWhenX[u.a1] = max(maxWhenX[u.a1], u.val);
            maxWhenX[u.a2] = max(maxWhenX[u.a2], u.val);
            //cout << u.a1 << " " << u.a2 << " " << u.val << endl;
        }
    }
    res = res + max(m, point[a.back()][a.back()] + 1);
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 19276
#include <iostream>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
const int MAX=10000;

int main(){
	int N;
	cin>>N;
	cout<<1110-N;
}

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

int main() {
  int x, n;
  cin >> x >> n;
  vector<bool> h(102);
  rep(i,n){
    int p;
    cin >> p;
    h[p] = true;
  }
  pair<int,int> ans(100000,-1);
  for(int i=0; i<=101; i++){
    if(h[i]) continue;
    int dif = abs(x-i);
    ans = min(ans, pair<int,int>(dif, i));
  }
  cout << ans.second << endl;
}


Measured memory_bytes: 3628
N = int(input())
A = list(map(int, input().split()))
B = [[] for i in range(N)]
ans = [0]*N
for k, a in enumerate(A):
    a = a - 1
    B[a].append(k)


S = 0
for b in B:
    lenb = len(b)
    if lenb >= 1:
        S += lenb * (lenb-1) / 2

for i, b in enumerate(B):
    for j, k in enumerate(b):
        ans[k] = int(S - (len(b) - 1))
for i in ans:
    print(i)

Measured memory_bytes: 47064
import java.util.*;
import java.io.*;
public class Main
{
  public static void main(String [] args)
  {
    Scanner sc=new Scanner(System.in);
    int N=sc.nextInt();
    if(N%10==2 || N%10==4 || N%10==5 || N%10==7 || N%10==9)
      System.out.print("hon");
    else if(N%10==0 || N%10==1 || N%10==6 || N%10==8)
      System.out.print("pon");
    else if(N%10==3)
      System.out.print("bon");
  }
}

Measured memory_bytes: 27088
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ep emplace_back
#define st first
#define sc second

using namespace std;

const ll mod = 998244353;
const int e = 1e6 + 69;
const int base = 311;

// dung igt thay cho gt luc tinh giai thua
// 3
// cach tao hoan vi tu n so : n*(n+1)/2;

struct kien
{
    ll x, y;
};
kien a[e];

bool lf(const kien &p, const kien &q)
{
    return p.x <q.x;
}

int main()
{
   ll a, b;
   cin >> a >> b;
   a--;
   if(a % 4 == 0)
   {
       a = a;
   }
   else if(a % 4 == 1) a = 1;
   else if(a % 4 == 2) a ++;
   else a = 0;
   if(b % 4 == 0)
   {
       b = b;
   }
   else if(b % 4 == 1) b = 1;
   else if(b % 4 == 2) b ++;
   else b = 0;
   ll k = a ^ b;
   cout << k;
}


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

using namespace std;

const int MOD = 1e9 + 7;

void add_self(int &a, int b){
    a += b;
    if(a >= MOD){
        a -= MOD;
    }
}

const int EQUAL = 0;
const int LESSER = 1;
const int DMAX = 105;

int main(){
    int d;
    string s;
    cin >>s>> d; 
    
    int dp[2][DMAX], new_dp[2][DMAX];
    
    for(int i = 0; i < 2; ++i){
        for(int j = 0; j < d; ++j){
            dp[i][j] = 0;
            new_dp[i][j] = 0;
        }
    }
    
    int n = s.length();
    dp[EQUAL][0] = 1;
    for(int i = 0; i < n; ++i){
        int act_digit = s[i] - '0';
        for(int digit = 0; digit <= 9; ++digit){
            for(int prev_state = 0; prev_state < d; ++prev_state){
                int new_d = (prev_state + digit) % d;
                
                add_self(new_dp[LESSER][new_d], dp[LESSER][prev_state]);
                if(digit < act_digit){
                    add_self(new_dp[LESSER][new_d], dp[EQUAL][prev_state]);
                }else if(digit == act_digit){
                    add_self(new_dp[EQUAL][new_d], dp[EQUAL][prev_state]);  
                }
            }
        }
        
        for(int i = 0; i < d; ++i){
            dp[0][i] = new_dp[0][i];
            dp[1][i] = new_dp[1][i];
            new_dp[0][i] = 0;
            new_dp[1][i] = 0;
        }
    }
    
    int ans = dp[EQUAL][0];
    add_self(ans, dp[LESSER][0]);
    ans--;
    if(ans == -1){
        ans = MOD - 1;
    }
    cout << ans << "\n";
    
    return 0;
}

Measured memory_bytes: 3680
#include <bits/stdc++.h>
using namespace std;
 
// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
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 int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
 
 
 
signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,m; cin>>n>>m;
  priority_queue<ll, vector<ll>, greater<ll>> q;
  rep(i,n){
    ll a; cin>>a;
    q.push(a);
  }
  vector<pll> v;
  rep(i,m){
    ll b,c; cin>>b>>c;
    v.emplace_back(c,b);
  }
  sort(v.rbegin(),v.rend());
  rep(i,m){
    ll a=q.top();
    if(a>=v[i].first) break;
    rep(j,v[i].second){
      a=q.top();
      if(a>=v[i].first) break;
      q.pop();
      q.push(v[i].first);
    }
  }
  ll ans=0;
  while(!q.empty()){
    ans+=q.top();q.pop();
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3316
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
	double a, b, h, m;
	cin >> a >> b >> h >> m;
	// deg is rad
	double deghour = 2 * M_PI * (h / 12 + m / 12 / 60);
	double degmin = 2 * M_PI * m / 60;
	double degdiff = deghour - degmin;

	double d = sqrt(a*a + b*b - 2*a*b*cos(degdiff));
	cout << std::setprecision(20) << d << endl;

	return 0;
}


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

struct cake{
    int w,h;
    cake(){
        w = 0;
        h = 0;
    }
    cake(int w, int h){
        this->w = w;
        this->h = h;
    }
};

int main() {

    while(true){

        int n,w,d;

        cin >> n >> w >> d;

        if(n == w && w == d && d == 0){
            break;
        }

        cake start(w,d);

        list<cake> lc;

        lc.push_back(start);

        for(int loop=0; loop<n; loop++){

            int p,s;

            cin >> p >> s;

            list<cake>::iterator cut = lc.begin();

            for(int i=0; i<p-1; i++){
                cut++;
            }

            int l = cut->w * 2 + cut->h * 2;

            int sm = s % l;

            cake first,second;

            if((sm < cut->w)){
                int cw1 = sm;
                int cw2 = cut->w-sm;
                first.w = cw1;
                second.w = cw2;
                first.h = second.h = cut->h;
                if(first.w * first.h > second.w * second.h){
                    swap(first,second);
                }
                lc.push_back(first);
                lc.push_back(second);
            }
            else if(sm > (cut->w + cut->h) && sm < (cut->w*2 + cut->h)){ //垂直に切る
                sm -= cut->w + cut->h;
                int cw1 = sm;
                int cw2 = cut->w-sm;
                first.w = cw1;
                second.w = cw2;
                first.h = second.h = cut->h;
                if(first.w * first.h > second.w * second.h){
                    swap(first,second);
                }
                lc.push_back(first);
                lc.push_back(second);
            }
            else if(sm > cut->w && sm < (cut->w + cut->h)){
                sm -= cut->w;
                int ch1 = sm;
                int ch2 = cut->h-sm;
                first.h = ch1;
                second.h = ch2;
                first.w = second.w = cut->w;
                if(first.w * first.h > second.w * second.h){
                    swap(first,second);
                }
                lc.push_back(first);
                lc.push_back(second);
            }
            else{
                sm -= cut->w * 2 + cut->h;
                int ch1 = sm;
                int ch2 = cut->h-sm;
                first.h = ch1;
                second.h = ch2;
                first.w = second.w = cut->w;
                if(first.w * first.h > second.w * second.h){
                    swap(first,second);
                }
                lc.push_back(first);
                lc.push_back(second);
            }

            lc.erase(cut);

        }

        priority_queue<int> q;

        for(cake c : lc){
            q.push(-(c.h * c.w));
        }

        int siz = q.size();

        for(int i=0; i<siz - 1; i++){
            cout << -q.top() << " ";
            q.pop();
        }

        cout << -q.top() << endl;

    }

    return 0;
}


Measured memory_bytes: 3092