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

int main(void)
{
	int n;
	
	while (scanf("%d", &n) * n != 0){
		double data[4000] = {0};
		int i;
		int flag = 0;
		
		for (i = 0; i < n; i++){
			int id, price, num;
			
			scanf("%d %d %d", &id, &price, &num);
			if (data[id - 1] != -1){
				data[id - 1] += (double)price * num;
				if (data[id - 1] >= 1e6){
					flag = 1;
					printf("%d\n", id);
					data[id - 1] = -1;
				}
			}
		}
		if (flag == 0){
			puts("NA");
		}
	}
	
	return 0;
}

Measured memory_bytes: 648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int mod = 1e9 + 7;
const int inf = 2e9;
const ll linf = 9e18;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    int a = 0, b = 0, ba = 0;
    int ans = 0;
    rep(i, 0, n) {
        cin >> s[i];
        int len = s[i].size();
        rep(j, 0, len - 1) {
            if (s[i].substr(j, 2) == "AB") {
                ans++;
            }
        }
        if (s[i][0] == 'B' && s[i][len - 1] != 'A') {
            b++;
        }
        if (s[i][0] != 'B' && s[i][len - 1] == 'A') {
            a++;
        }
        if (s[i][0] == 'B' && s[i][len - 1] == 'A') {
            ba++;
        }
    }

    if (a == 0 && b == 0) {
        ans += max(ba - 1, 0);
    } else {
        ans += min(a + ba, b + ba);
    }

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


Measured memory_bytes: 896
#include <bits/stdc++.h>
#include <cstdlib> 
using namespace std;
 
int main() {
  string str;
  cin >> str;
  int cp,fp;
  cp = -1;
  fp = -1;
 
  for(int i = 0; i < str.size(); i++){
   if(str.at(i) == 'C'){
       cp = i;
       break;
    }
  }
    
  for(int i = 0; i < str.size(); i++){
   if(str.at(i) == 'F'){
       fp = i;
    }
  }
    
  if(cp == -1 || fp == -1){
       cout << "No" << endl;  
    }
  else if(cp < fp){
       cout << "Yes" << endl;
    }
  else{
       cout << "No" << endl;
   }
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define gc getchar
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define x1 uvuvwevwevwe
#define y1 onyetenyevwe
#define x2 ugwemubwem
#define y2 ossas
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
template <typename T> void scan(T &angka){
	angka=0;char input=gc();T kali=1;
	while(!(48<=input&&input<=57)){	if(input=='-')	kali=-1;input=gc();}
	while(48<=input&&input<=57)	angka=(angka<<3)+(angka<<1)+input-48,input=gc();angka*=kali;
}
template <typename T1,typename T2> void scan(T1 &angka1,T2 &angka2){
	scan(angka1);scan(angka2);
}
const int MAXN=100000;
int n;
LL dp[MAXN+5],C,ans=0;
vector <pair<LL,LL> > daftar;
void balik(){
	for(int i=0;i<daftar.size();i++)
		daftar[i].fi=C-daftar[i].fi;
	reverse(all(daftar));
}
int main()
{
	scan(n,C);
	daftar.resize(n);
	for(int i=0;i<n;i++)
		scan(daftar[i].fi,daftar[i].se);
	for(int ulang=0;ulang<2;ulang++)
	{
		LL temp=0;
		for(int i=0;i<n;i++)
		{
			temp+=daftar[i].se;
			dp[i]=temp-daftar[i].fi;
			if(i)
				dp[i]=max(dp[i],dp[i-1]);
		}
		ans=max(ans,dp[n-1]);
		
		temp=0;
		for(int i=n-1;i>=1;i--)
		{
			LL jarak=2*(C-daftar[i].fi);
			temp+=daftar[i].se;
			ans=max(ans,dp[i-1]+temp-jarak);
		}
		balik();
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 2560
/*
 *  author : Atul Anand   
 *  created on : Tue Mar 31 2020
 */

import java.io.*;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException {
        String S = in.next();
        if(S.charAt(0) == S.charAt(1) && S.charAt(1) == S.charAt(2)){
            println("No");
        }
        else{
            println("Yes");
        }    
        in.close();
        out.close();
    }

    static int MIN = Integer.MIN_VALUE;
    static int MAX = Integer.MAX_VALUE;
    static Reader in = new Reader();
    static PrintWriter out = new PrintWriter(System.out);

    static void read(int arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextInt(); 
    	} 
    }
    
    static void read(long arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextLong(); 
    	} 
    }
    
    static void read(String arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.next(); 
    	} 
    }
    
    static void print(Object O) {  
    	out.print(O); 
    }
    
    static void println(Object O) { 
    	out.println(O); 
    }
    
    static void println(int arr[]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		print(arr[i]+" "); 
    	} 
    	println(""); 
    }

    static void println(int arr[][]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		println(arr[i]); 
    	}
    }
    
    static void debug(Object O) { 
    	System.out.println(O); 
    }
}

class Reader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    Reader() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    String next() throws IOException {
        while (!tokenizer.hasMoreTokens() ) { 
            tokenizer = new StringTokenizer(reader.readLine()); 
        }
        return tokenizer.nextToken();
    }

    int nextInt() throws IOException { 
        return Integer.parseInt(next()); 
    }
    
    double nextDouble() throws IOException { 
        return Double.parseDouble(next());
    }
    
    long nextLong() throws IOException { 
        return Long.parseLong(next()); 
    }
    
    String nextLine() throws IOException { 
        return reader.readLine(); 
    }
    
    void close() throws IOException { 
        reader.close(); 
    }
}

Measured memory_bytes: 23252
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {

  static int n;
  static long ans;
  static int[] dp;
  static int[] op;
  static String x;

  public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);

    String[] in = br.readLine().split(" ");
    n = Integer.parseInt(in[0]);

    x = br.readLine();

    br.close();

    op = new int[n+1];

    dp = new int[200001];

    dp[0] = 0;

    for (int i = 1; i <= 200000; i++) {
      dp[i] = dp[i % Integer.bitCount(i)] + 1;
    }

    int initBit = 0;

    for (int i = 0; i < n; i++) {
      if (x.charAt(i) == '1') {
        initBit++;
      }
    }

    int u = 0, l = 0;

    for (int i = 0; i < n; i++) {
      u = 2 * u + (x.charAt(i) - '0');
      l = 2 * l + (x.charAt(i) - '0');
      u %= initBit+1;
      if(initBit > 1){
        l %= initBit-1;
      }
    }

    int adu = 1%(initBit+1), adl = 0;
    if (initBit > 1) adl = 1 % (initBit-1);

    for (int i = n-1; i >= 0; i--) {

      if (x.charAt(i) == '0') {
        op[i] = dp[(u + adu) % (initBit + 1)] + 1;
      } else {
        if (initBit > 1) {
          op[i] = dp[(l - adl + initBit - 1) % (initBit - 1)] + 1;
        } else {
          op[i] = 0;
        }
      }

      adu = (adu * 2) % (initBit + 1);
      if(initBit > 1) adl = (adl * 2) % (initBit - 1);

    }

    for (int i = 0; i < n; i++) {
      out.println(op[i]);
    }

    out.flush();
  }
}

Measured memory_bytes: 47360
def is_even_list(A):
    for a in A:
        if (int(a) % 2 == 1):
            return False
    return True

def divide_list(A):
    newA = []
    for a in A:
        newA.append(int(a) / 2)
    return newA

N = int(input())
A = input().split()
count = 0

while(is_even_list(A)):
    A = divide_list(A)
    count += 1
print(count)

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

int main() {
    std::string s;
    std::cin >> s;
    int k;
    std::cin >> k;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] != '1') {
            std::cout << s[i] << std::endl;
            return 0;
        }
        if (i == k - 1) {
            std::cout << 1 << std::endl;
            return 0;
        }
    }
}


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

using namespace std;

int N, M;
string A[50];
string B[50];

inline bool is_include(int posi, int posj) {
  int ti;
  for(int i=0; i<M; i++) {
    ti = i+posi;
    for(int j=0; j<M; j++) {
      if(A[ti][posj+j] != B[i][j]) {
        return false;
      }
    }
  }
  return true;
}


int main() {
  cin >> N >> M;
  cin.ignore();
  for(int i=0; i<N; i++) {
    getline(cin, A[i]);
  } 

  for(int i=0; i<M; i++) {
    getline(cin, B[i]);
  }

 
  const int size=N-M;

  for(int i=0; i<=size; i++) {
    for(int j=0; j<=size; j++) {
      if(is_include(i, j)) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

int main(){
    int n, i, k, count;
    float sqr;
    int input_list[10000];
    
    scanf("%d", &n);
    
    for(i = 0; i < n; i++){
        scanf("%d", &input_list[i]);
    }
    
    count = 0;
    for(i = 0; i < n; i++){
        sqr = sqrt(input_list[i]);
        for(k = 2; k <= sqr; k++){
            if(input_list[i] % k == 0){
                break;
            }
        }
        if(k > (int)sqr){
            count++;
        }
    }
    printf("%d\n", count);
    
    return 0;
}


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

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mem(x,n) memset(x,n,sizeof(x))
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define foreach(it,l) for(auto it=(l).begin();it!=(l).end();it++)
#define pnl printf("\n")
#define len(x) (x).length()

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const double EPS=1e-10;
//const double PI=acos(-1.0);
const int INF=1<<30;
const LL LLINF=1ll<<60;
const int MOD=1e9+7;
const int xx[8]={1,0,-1,0,1,-1,1,-1};
const int yy[8]={0,1,0,-1,-1,1,1,-1};

/****************************************************************************************\
 __    __               __ /\/|   ___ _           _       /\/|__               __    __
 \ \  / /  _____ __ ____\ \/\/   / __| |__ _ _ __(_)___  |/\// /____ __ _____  \ \  / /
  \ \| |  |___\ V  V /___| |    | (__| / _` | '_ \ / -_)    | |___\ V  V /___|  | |/ /
   \_\ |  |___|\_/\_/|___| |     \___|_\__,_| .__/_\___|    | |___|\_/\_/|___|  | /_/
      \_\               /_/                 |_|              \_\               /_/
\****************************************************************************************/

struct pip{
	LL p,h;
}p[5005];

LL memo[5005][5005];
int n;

bool comp(pip a,pip b){
	if(a.p!=b.p) return a.p+a.h<b.p+b.h;
	return a.h<b.h;
}

void reset(){
	for(int i=0;i<5005;i++){
		for(int j=0;j<5005;j++){
			memo[i][j]=LLINF;
		}
	}
}

int main(){
	reset();
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&p[i].h,&p[i].p);
	}
	sort(p+1,p+n+1,comp);
	
	int ans=0;
	
	memo[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(memo[i-1][j-1]<=p[i].h) memo[i][j]=min(memo[i-1][j-1]+p[i].p,memo[i-1][j]);
			else memo[i][j]=memo[i-1][j];
		}
	}
	
	for(int i=n;i>0;i--){
		for(int j=n;j>0;j--){
			if(memo[i][j]!=LLINF){
				printf("%d\n",j);
				return 0;
			}
		}
	}
}

Measured memory_bytes: 195968
#include<bits/stdc++.h>
using namespace std; 
typedef long long int ll;
const long long int m=pow(10,9)+7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    unsigned long long int n,ans=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        ans+=a[i]-1;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3692
package main

import (
	"fmt"
)

func main() {
	var s, t string
	fmt.Scan(&s, &t)
  
  cnt := 0
  for i := 0; i < len(s); i++ {
    if s[i] != t[i] {
      cnt++
    }
  }
  fmt.Println(cnt)
  
}

Measured memory_bytes: 3388
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int bits = 62;

template <int bits = 62>
ll solveXorMax(vector<ll> A) {
  int N = A.size(), r = 0;
  for (int b = bits - 1; b >= 0; b--) {
    int p = -1;
    for (int i = r; i < N; i++) {
      if ((A[i] >> b) & 1) {
        p = i;
        break;
      }
    }
    if (p == -1) continue;
    swap(A[p], A[r]);
    for (int i = 0; i < N; i++) {
      if (i != r && ((A[i] >> b) & 1)) A[i] ^= A[r];
    }
    ++r;
  }
  ll res = 0;
  for (ll x : A) {
    if ((res ^ x) > res) res ^= x;
  }
  return res;
}

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N;
  while (cin >> N) {
    vector<ll> A(N);
    for (ll& x : A) cin >> x;
    ll S = 0;
    for (ll x : A) S ^= x;
    vector<ll> B(N);
    int k = 0;
    for (int b = bits - 1; b >= 0; b--) {
      if ((S >> b) & 1) continue;
      for (int i = 0; i < N; i++) B[i] = B[i] * 2 + ((A[i] >> b) & 1);
      ++k;
    }
    ll mx = solveXorMax(B);
    ll res = 0;
    for (int b = bits - 1; b >= 0; b--) {
      if ((S >> b) & 1) {
        res *= 2;
      } else {
        --k;
        res = res * 2 + ((mx >> k) & 1);
      }
    }
    res = res * 2 + S;
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i <= (n); i++)
#define repi(i,a,b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;

int main() {
  int A, B;
  cin >> A >> B;
  
  if (A == 1) A = 14;
  if (B == 1) B = 14;
  
  if (A > B) 
    cout << "Alice" << endl;
  else if (A < B)
    cout << "Bob" << endl;
  else
    cout << "Draw" << endl;
}

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

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

typedef pair<int, int> pint;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front

#define MOD (1000 * 1000 * 1000 + 7)

signed main() {
    ll N;
    cin >> N;

    ll mid = 0;
    while (true) {
        if (mid * mid > N) {
            mid--;
            break;
        }
        mid++;
    }

    while (true) {
        if (N % mid == 0) {
            ll a = N / mid;

            ll ans = (a + mid) - 2;
            cout << ans << endl;

            break;
        }
        mid--;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<functional>
#include<string>
using namespace std;

const int dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
char fld[12][12];

void dfs(int y,int x){
	int ny,nx;
	for(int i=0;i<4;i++){
		ny = y+dy[i];
		nx = x+dx[i];
		if(ny<0 || 12<=ny || nx<0 || 12<=nx || fld[ny][nx]=='0') continue;
		fld[ny][nx]='0';
		dfs(ny,nx);
	}
}

int main(){
	while(cin>>fld[0][0]){
		for(int i=0;i<12;i++){
			for(int j=0;j<12;j++){
				if(i==0 && j==0) continue;
				cin>>fld[i][j];
			}
		}
		int ans=0;
		for(int i=0;i<12;i++){
			for(int j=0;j<12;j++){
				if(fld[i][j]=='1'){
					fld[i][j]='0';
					dfs(i,j);
					ans++;
				}
			}
		}
		printf("%d\n",ans);
	}
    return 0;
}

Measured memory_bytes: 1124
//In The Name Of God
#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define mp make_pair
#define L(x) (2*(x))
#define R(x) ((2*(x))+1)
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int N = 2e6 + 5, Mod = 1e9 + 7, P = 727, Lg = 22, TOF = 1900;

int Dp[N], H[N];
int32_t main(){
      ios_base::sync_with_stdio(0); cin.tie(0);
      int n, k; cin >> n >> k;
      for(int i = 1; i <= n; i++)
            cin >> H[i];
      for(int i = 2; i <= n; i++){
            Dp[i] = Dp[i - 1] + abs(H[i] - H[i - 1]);
            for(int j = 2; j < min(i, k + 1); j++)
                  Dp[i] = min(Dp[i], Dp[i - j] + abs(H[i] - H[i - j]));
      }
      cout << Dp[n];
      return 0;
}



Measured memory_bytes: 5120
#include <bits/stdc++.h>
#include <cstdio>
#include <cmath>

using namespace std;


int n;
double x[1005], y[1005], X, Y, d, e;
double dist(double a, double b) {
	return a*a + b*b;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lf%lf", &x[i], &y[i]);
		X += x[i]; Y += y[i];
	}
	X /= n; Y /= n;
	double P = 0.1;
	for (int i = 0; i < 30000; i++) {
		int f = 0;
		d = dist(X - x[0], Y - y[0]);
		for (int j = 1; j < n; j++) {
			e = dist(X - x[j], Y - y[j]);
			if (d < e) { d = e; f = j; }
		}
		X += (x[f] - X)*P;
		Y += (y[f] - Y)*P;
		P *= 0.999;
	}
	cout << setprecision(10) << sqrt(d);
}


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

using namespace std;
const long long MOD = (long long)1e9 + 7;
long long dp[4][100010];

int main(){
	string s;
	cin >> s;
	dp[0][0] = 1;
	for(int i = 0; i < s.size(); i++){
		for(int j = 0; j < 4; j++){
			if(s[i] == '?'){
				dp[j][i + 1] += dp[j][i] * 3;
				if(j < 3){
					dp[j + 1][i + 1] += dp[j][i] * 1;
				}
			}else{
				if(s[i] == 'A' + j){
					dp[j + 1][i + 1] += dp[j][i] * 1;
				}
				dp[j][i + 1] += dp[j][i] * 1;
			}
			dp[j][i + 1] %= MOD;
			if(j < 3){
				dp[j + 1][i + 1] %= MOD;
			}
		}
	}
	cout << dp[3][s.size()] << endl;
	return 0;
}

Measured memory_bytes: 3584
// atcoder/abc135/D/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

const lli mod = 1e9 + 7;

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  string s;
  while (cin >> s) {
    vector<int> v;
    const lli N = 1e5 + 5;
    const int M = 13;
    static lli dp[N][M];
    fill(&dp[0][0], &dp[N - 1][M - 1] + 1, 0);
    dp[0][0] = 1;
    for (int i = 0; i < s.size(); ++i) {
      for (int j = 0; j < M; ++j) {
        if (s[i] == '?') {
          for (int k = 0; k <= 9; ++k) {
            (dp[i + 1][(j * 10 + k) % M] += dp[i][j]) %= mod;
          }
        } else {
          (dp[i + 1][(j * 10 + s[i] - '0') % M] += dp[i][j]) %= mod;
        }
      }
    }
    cout << dp[s.size()][5] << endl;
  }

  return 0;
}


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

//---------------------------------------------------------------
// ------ disjoint set ------ //
struct UnionFind {
    vector<int> data;
    int __size;
    UnionFind(int size) : data(size, -1), __size(size) { }
    bool unionSet(int x, int y) {
        if ((x = root(x)) != (y = root(y))) {
            if (data[y] < data[x]) swap(x, y);  // par -> child とは限らない
            data[x] += data[y]; data[y] = x; __size--;
        }
        return x != y;
    }
    bool findSet(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
    int size() { return __size; }
    vector<int> subset_roots() {
        vector<int> roots;
        for (int i = 0; i < data.size(); i++) if (data[i] < 0) roots.push_back(i);
        return roots;
    }
};
//---------------------------------------------------------------

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

int encode(int i, int j) { return i * w + j; }
bool exterior(int i, int j) { return i < 0 || h <= i || j < 0 || w <= j; }

void bfs(vector<vector<int>> &fi, int num) {
    queue<int> q; q.push(encode(0, 0));
    int color = fi[0][0];
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        int i = cur / w, j = cur % w;
        fi[i][j] = num;
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k], nj = j + dy[k];
            if (exterior(ni, nj)) continue;
            if (fi[ni][nj] == color && fi[ni][nj] != num) q.push(encode(ni, nj));
        }
    }
}

int solve(vector<vector<int>> fi, vector<int> nums) {
    for (int i = 0; i < 5; i++) bfs(fi, nums[i]);
    UnionFind uf(w * h);
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        int ij = encode(i, j);
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k], nj = j + dy[k];
            if (exterior(ni, nj)) continue;
            int nij = encode(ni, nj);
            if (fi[i][j] == fi[ni][nj]) uf.unionSet(ij, nij);
        }
    }
    return uf.size(encode(0, 0));
}

int main() {
    int c;
    while (cin >> h >> w >> c, h) {
        vector<vector<int>> field(h, vector<int>(w));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> field[i][j];
            }
        }
        int ans = 0;
        for (int x = 1; x <= 6; x++) {
            for (int y = 1; y <= 6; y++) {
                for (int z = 1; z <= 6; z++) {
                    for (int w = 1; w <= 6; w++) {
                        ans = max(ans, solve(field, vector<int>{x, y, z, w, c}));
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3172
import bisect

n,m = map(int,input().split())
a = list(map(int,input().split()))
s = []
for i in range(m):
    b,c = map(int,input().split())
    s.append((c,b))

a.sort()
s.sort(reverse=True)

for i in range(m):
    b = s[i][1]
    c = s[i][0]
    idx = bisect.bisect_left(a,c)
    if idx == 0:
        break
    del a[0:min(b,idx)]
    for j in range(min(b,idx)):
        a.insert(bisect.bisect_left(a,c),c)

print(sum(a))
    

Measured memory_bytes: 26996
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)

int main(){
  int64_t N;
  cin >> N;
  vector<int64_t> A(N+1);
  A.at(0) = 0;
  rep(i, N){
    cin >> A.at(i+1);
  }
  long double len = 0;
  rep(i, N){
    len += A.at(i+1);
  }
  long double cen = len/2;
  int64_t tmp1 = 0;
  int64_t tmp2 = 0;
  int64_t pos = 0;
  while(tmp1 < cen){
    tmp1 += A.at(pos+1);
    tmp2 += A.at(pos);
    pos++;
  }
  if(tmp1 == cen){
    cout << 0 << endl;
  }
  else if(cen - tmp2 <= tmp1 - cen){
    cout << (int64_t)(2 * (cen - tmp2)) << endl;
  }
  else{
    cout << (int64_t)(2 * (tmp1 - cen)) << endl;
  }
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
struct node{
    int l, r;
};

string s;
int n;

vector<node>a;
vector<node>b;

bool cmp(node x, node y){
    return x.r < y.r;
}

bool cmp1(node x, node y){
    return x.l > y.l;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> s;
        int len = s.length();
        int l =0, r = 0;
        for(int j = 0; j < len; j++){
            if(s[j] == '(') l++;
            else if(l) l--;
            else r++;
        }
        if(l >= r) a.push_back({l, r});
        else b.push_back({l, r});
    }
    sort(a.begin(), a.end(), cmp);
    sort(b.begin(), b.end(), cmp1);
    int sum = 0, ok = 0;
    for(int i = 0; i < a.size(); i++){
        sum -= a[i].r;
        if(sum < 0){
            ok = 1;
            break;
        }
        sum += a[i].l;
    }
    int sum1 = 0;
    for(int i = 0; i < b.size(); i++){
        sum -= b[i].r;
        if(sum < 0){
            ok = 1;
            break;
        }
        sum += b[i].l;
    }
    if(ok){
        cout << "No \n"; 
    }else{
        if(sum == 0){
            cout << "Yes\n";
        }else{
            cout << "No\n";
        }
    }

}

Measured memory_bytes: 11132
#include <stdio.h>

int main(void) {
  
  char s[11];
  scanf("%s", s);
  
  int max_len = 0, current_len;
  int len = strlen(s);
  for(int i = 0; i < len; ++i) {
    
    if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') ++current_len;
    else {
      if(current_len > 0) {
        if(current_len > max_len) max_len = current_len;
        current_len = 0;
      }
    }
    
  }
  
  if(current_len > max_len) max_len = current_len;
  
  printf("%d\n", max_len);
  
  return 0;
  
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T> inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();
    
    int w, h;
    cin >> w >> h;
    priority_queue<pair<int, int>> q;
    int in;
    FOR(i, 0, w) {
        cin >> in;
        if(in)q.push({ in,i });
    }

    FOR(i, 0, h) {
        cin >> in;
        if (q.size() < in) {
            cout << "0\n";
            return 0;
        }
        priority_queue<pair<int, int>> p;
        while (!q.empty()) {
            int num, itr;
            tie(num, itr) = q.top(); q.pop();
            if (in)in--, num--;
            if(num)p.push({ num,itr });
        }
        swap(p, q);
    }
    cout << "1\n";
}


Measured memory_bytes: 3240
#include <iostream>
using namespace std;


int main(){
    int N;
    cin >> N;
    int d[50];
    for(int i=0; i<N; i++){
        cin >> d[i];
    }

    int answer = 0;

    for(int j=0; j<N-1; j++){
        for(int k=j+1; k<N; k++){
            answer += d[j]*d[k];
        }
    }

    cout << answer;
    
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    l = [tuple(map(int, input().split())) for _ in range(M)]
    l = list(set(l))   # 重複する条件は削除する
    s_num = []
    if N == 1:
        ans = [0]
        for s, c in l:
            s -= 1
            if s in s_num:
                print(-1)
                exit()
            s_num.append(s)
            ans[s] = c
    else:
        ans = [1] + [0] * (N - 1)
        for s, c in l:
            s -= 1
            if s in s_num:  # 変更回数が2回になったらだめ
                print(-1)
                exit()
            if s == 0 and c == 0:  # 先頭の数字が0のときはだめ
                print(-1)
                exit()
            s_num.append(s)
            ans[s] = c
    print(*ans, sep='')


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <iostream>
#include<iomanip>
#include<vector>
#include<cmath>

using namespace std;
int main(void){
    int x[3];
    cin >> x[0] >> x[1] >> x[2];
    if(x[0]==x[1] && x[1] == x[2])
      cout << "Yes\n";
    else
      cout << "No\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
  int a, b;
  cin >> a >> b;
  if (13 <= a) {
    cout << b;
  } else if (6 <= a) {
    cout << (b >> 1);
  } else {
    cout << 0;
  }
  cout << endl;
  return 0;
}


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

int main(){
    string S;
    cin >> S;
    int N = S.size();
    int ans = 0;
    for (int i = 2; i < N; i += 2){
        if (S.substr(0,i / 2) + S.substr(0,i / 2) == S.substr(0,i)){
            ans = i;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int ctoi(char c) {return c-'0';}// char to int
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}//MAX
int lcm(ll a,ll b){return a*b/gcd(a,b);}//MIN
 
int  main(){
int a,b;
cin >> a >> b;
cout << 6- a-b<<endl;
}
 


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
  ll sx,sy,tx,ty;cin>>sx>>sy>>tx>>ty;
  string ans="";
  rep(i,ty-sy)ans+='U';
  rep(i,tx-sx)ans+='R';
  rep(i,ty-sy)ans+='D';
  rep(i,tx-sx)ans+='L';
  ans+='L';
  rep(i,ty-sy+1)ans+='U';
  rep(i,tx-sx+1)ans+='R';
  ans+='D';
  ans+='R';
  rep(i,ty-sy+1)ans+='D';
  rep(i,tx-sx+1)ans+='L';
  ans+='U';
  cout<<ans<<endl;
}

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

def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

max_k = gcd(A_arr[0], A_arr[1])
if N > 2:
    for i in range(2, N):
        max_k = gcd(max_k, A_arr[i])
else:
    pass

print(max_k)

Measured memory_bytes: 14252
from sys import stdin,stdout
Pi = lambda x: stdout.write(str(x) + '\n')
S = lambda x: x*(x+1) // 2
I = lambda x: 1+(2*x)
R = lambda:stdin.readline()
Ri = lambda x:map(int,x.split())
Rs = lambda x:map(str,x.split())
Rf = lambda x:map(float,x.split())
 
def main():	
	# t = int(R())
	for x in stdin:
		k,n = Ri(x)
		A = list(Ri(R()))
		ans = A[-1] - A[0]
		for i in range(n-1):
			ans = min(ans, (A[i]-A[0]) + (k-A[i+1]+A[0]))
			# Pi(ans)
		
		Pi(ans)

if __name__=='__main__':
	main()

Measured memory_bytes: 71248
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int pre[100005];
int main()
{
  	int n , k;
 	cin >> n >> k;
  	long long a[n];
  	for(int i = 0 ; i < n ; i++)
      cin >> a[i];
  	sort(a , a + n);
  	long long ans = 9999999999;
  	for(int i = 0 ; i < n - k + 1 ; i++){
		ans = min(ans , (a[i + k - 1] - a[i]));
    }
	cout << ans << endl;  
  	return 0;
}

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



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



}

Measured memory_bytes: 3612
/**-------------------------
|--------From A.R.A--------|
-------------------------**/

#include <bits/stdc++.h>

#define ll            long long int
#define pb            push_back
#define ull           unsigned long long int
#define endl          "\n"
#define sz(c)         (c).size()
#define sall(c)       sort((c).begin(),(c).end())
#define rsall(c)      sort((c).rbegin(),(c).rend())
#define rev(c)        reverse((c).begin(),(c).end())
#define FOR(i,n)      for(ll i=0;i<n;i++)
#define max3(a,b,c)   max(max(a,b),c)
#define min3(a,b,c)   min(min(a,b),c)
#define input(a,i,n)  for(ll i=0;i<n;i++){      cin>>a[i];}
#define output(a,i,n) for(ll i=0;i<n;i++){cout<<a[i]<<" ";}

using namespace std;

int R=1;
void solution(){
    int64_t a,b1;
    long double b;
    cin>>a>>b;
    b1=(int64_t)a*b;
    cout<<b1<<endl;
}
int main()
{
    //cin>>R;
    FOR(i,R){solution();}
    return 0;
}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int N;
int A[100010];

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

	cin >> N;
	rep(i, 0, N)
	{
		cin >> A[i];
	}

	bool ok = true;
	rep(i, 0, N-1)
	{
		if (A[i] > A[i + 1])
		{
			if (A[i] - A[i + 1] >= 2)
			{
				ok = false;
				break;
			}
			A[i + 1]++;
		}
	}

	if (ok)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 1024
float o(float*a,float*b,float*c){return a[1]*(*c-*b)+c[1]*(*b-*a)+b[1]*(*a-*c);}float x,p[8];i;main(){for(;~scanf("%f,",p+i++%8);)i%8||puts(x*o(p+2,p+4,p+6)>0&x*o(p+4,p+6,p)>0&x*o(p+6,p,p+2)>0?"YES":"NO",x=o(p,p+2,p+4));}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
int f[301][301];
int ix[100000],iy[100000];
int sum[100000];
signed main(){
	int h,w,d;
	cin>>h>>w>>d;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			int x;
			cin>>x;
			f[i][j] = x;
			ix[x] = i; iy[x] = j;
		}
	}
	for(int i=1;i<=h*w;i++){
		int cur = 0;
		if( i > d ){
			cur = sum[i-d]+ abs( ix[i] - ix[i-d] ) + abs( iy[i] - iy[i-d] );
		}
		sum[i] = cur;
	}
	int q; cin>>q;
	for(int i=0;i<q;i++){
		int lef,rig;
		cin>>lef>>rig;
		cout<<sum[rig]-sum[lef]<<endl;
	}
	return 0;
}

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

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

  vector<int64_t> L(n+1);

  L[0] = 2;
  L[1] = 1;

  for (int i = 2; i <= n; i++) {
    L[i] = L[i - 1] + L[i - 2];
  }

  cout << L[n] << endl;
}


Measured memory_bytes: 256
N = int(input())
T,A = list(map(int,input().split(" ")))
H = list(map(int,input().split(" ")))
res = 1000000
c = 1
for i in range(N):
    tmp = T-(H[i]*0.006)
    d = abs(tmp-A)
    if d < res:
        res = d
        c = i+1
print(c)





Measured memory_bytes: 3060
#include <iostream>
#include <cmath>
#define MAX 100000
using namespace std;
typedef long long ll;

ll fun(ll x, ll y) {
    if(y==0)
        return x;
    else
        return fun(y, x%y);
}

int main(void) {
    ll n, k, a, lar=0, g=0;
    cin >> n >> k;
    for(ll i=0; i<n; i++) {
        cin >> a;
        lar = max(lar, a);
        g = fun(g, a);
    }
    cout << (k%g || k>lar ? "IMPOSSIBLE" : "POSSIBLE");
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;


class Main{
	//今回は、価値は低くて、重さが大きいもののナップサック。
	//いままでは、価値をテーブルに格納していたが、今回は、同じ価値をできるだけ少ない重さで実現しようという計画。
	//その為、dpにminを使う
	public static void main(String[] args){
		SC sc=new SC(System.in);
		int N=sc.nextInt();
		int W=sc.nextInt();
		int[][] dp=new int[N+1][N*100+1];	//品物の番号、価値
		int INF=2000000014;
		for(int i=0; i<=N; i++){
			for(int j=0; j<=N*100; j++){
				dp[i][j]=INF;
			}
		}
		dp[0][0]=0;
		int[][] products=new int[N][2];
		for(int i=0; i<N; i++){
			products[i][0]=sc.nextInt();		//価値
			products[i][1]=sc.nextInt();		//重さ
		}

		for(int i=0; i<N; i++){
			for(int j=0; j<=N*100; j++){
				if(j-products[i][0]<0){
					dp[i+1][j]=dp[i][j];		//品物が買えないとき
				}
				else if(j-products[i][0]>=0 && dp[i][j-products[i][0]]+products[i][1]<=W){
					dp[i+1][j]=Math.min(dp[i][j], dp[i][j-products[i][0]]+products[i][1]);
				}
				else{
					dp[i+1][j]=dp[i][j];
				}
			}
		}
		int valmax=0;
		for(int i=0; i<=N*100; i++){
			if(dp[N][i]<=W){
				valmax=i;
			}
		}
		pl(valmax);
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> duo;

#define TT template<typename T>
TT T    sq(T x){ return x*x; }
TT int  ubnd(vector<T>& v,T x){ return upper_bound(v.begin(), v.end(), x) - v.begin(); }
TT int  lbnd(vector<T>& v,T x){ return lower_bound(v.begin(), v.end(), x) - v.begin(); }
TT void sort(T& v){ sort(v.begin(), v.end()); }
TT void revs(T& v){ reverse(v.begin(), v.end()); }
TT void uniq(T& v){ sort(v); v.erase(unique(v.begin(), v.end()), v.end()); }
TT void show(T& v,char d=' ',char e='\n'){for(int i=0;i<v.size();++i)cout<<v[i]<<((i==v.size()-1)?e:d);}
TT void inpt(vector<T>& v,int n){ v.reserve(n);for(int i=0;i<n;++i){T x; cin>>x; v.push_back(x);} }
TT T    In(T& x){ cin >> x; return x; }

static inline void fast_io(){ ios::sync_with_stdio(0); cin.tie(0); }
static inline int in(){ int x; scanf("%d", &x); return x; }
static inline string instr(){ string x; cin >> x; return x; }
static const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
static const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};

int main()
{
  const int inf = -10e8;
  int case_no = 1;
  int W;
  while (W = in()){
    int dp[1024];
    fill(dp, dp + 1024, inf);
    
    int n = in();
    dp[0] = 0;
    for (int i = 0; i < n; i++){
      int v, w;
      scanf("%d,%d", &v, &w);
      for (int i = W; i >= w; i--){
        dp[i] = max(dp[i], dp[i - w] + v);
      }
    }
    int min_w = W;
    for (int i = W; i >= 0; i--){
      if (dp[min_w] <= dp[i]) min_w = i;
    }
    printf("Case %d:\n", case_no);
    printf("%d\n%d\n", dp[min_w], min_w);
    case_no++;
  }
  return (0);
}

Measured memory_bytes: 1192
#include <array>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

constexpr int MAX_M = 11;

int m, n;
int memo[1 << MAX_M][1 << MAX_M];

int dfs(int used, int result, const vector<unsigned> &objects) {
	if(objects.size() <= 1) return 0;

	int &res = memo[used][result];
	if(res != -1) return res;
	res = MAX_M;

	for(int i = 0; i < m; ++i) {
		if((used >> i) & 1) continue;

		array<vector<unsigned>, 2> next_objects;
		for(const auto &e : objects) {
			next_objects[(e >> i) & 1].emplace_back(e);
		}

		const int yes = dfs(used | (1 << i), result | (1 << i), next_objects[1]);
		const int no = dfs(used | (1 << i), result, next_objects[0]);
		chmin(res, max(yes, no) + 1);
	}

	return res;
}

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

	while(cin >> m >> n && m) {
		vector<unsigned> objects(n);
		for(auto &e : objects) {
			bitset<MAX_M> b;
			cin >> b;
			e = b.to_ulong();
		}

		memset(memo, -1, sizeof(memo));
		cout << dfs(0, 0, objects) << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 17620
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 1000000007
#define INF 98765431219876543
#define bitcnt(a) (ll) __builtin_popcount((a))
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> TP;
typedef pair<string, string> PS;

int main(){
	double a,b;
	cin>>a>>b;
	cout<<a/b<<endl;
}

Measured memory_bytes: 256
from collections import defaultdict
n = int(input()) + 1
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

# 1を一つだけ選ぶやつは重複する可能性
d = defaultdict(int)

left = right = 0
for i in range(n):
    if d[a[i]] > 0:
        right = i
        left = a.index(a[i])
        break
    d[a[i]] += 1


fac = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % mod


def inv(x):
    return pow(x, mod - 2, mod)


def c(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * inv(fac[n - k] * fac[k] % mod) % mod


left_len = left
right_len = n - right - 1
print(n - 1)
for i in range(2, n + 1):
    ans = c(n, i) - (c(left_len + 1 + right_len, i) -
                     c(left_len + right_len, i))
    print(ans % mod)


Measured memory_bytes: 23988
N,M,X,Y = map(int, raw_input().split())
X_list = map(int,raw_input().split())
Y_list = map(int,raw_input().split())
X_list_max = max(X_list)
Y_list_min = min(Y_list)

Z_list = []

for i in range(X+1,Y+1):
    if i > X_list_max:
        Z_list.append(i)
ans = "War"

for i in Z_list:
    if i <= Y_list_min:
        ans = "No War"
        break

print ans

Measured memory_bytes: 2568
#include<iostream>
using namespace std;
int main()
{
	string s,t;
	cin>>s>>t;
	int i,j;
	char c;
	if(s==t){
		cout<<"Yes";
		return 0;
	}
	for(i=1;i<=s.size();i++){
		c=s[s.size()-1];
		for(j=s.size()-1;j>0;j--)
			s[j]=s[j-1];
		s[0]=c;
		if(s==t){
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N,M;
int c[101];
int main(){
	cin>>N>>M;
	REP(i,N){
		int K;
		cin>>K;
		REP(i,K){
			int a;
			cin>>a;
			c[a]++;
		}
	}
	int ans=0;
	REP(i,101){
		if(c[i]==N)ans++;
	}
	cout<<ans<<endl;
}

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int bucket[100000] = {0};

    for (int i = 0; i < n; ++i){
        int a;
        cin >> a;
        bucket[a]++;
    }
    int res = 0;
    for (int i = 2; i < 100000; ++i){
        res = max(res, bucket[i-2] + bucket[i-1] + bucket[i]);
    }
    cout << res << endl;
}

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

using namespace std;

int main(){
    long long int N,K,sum=0;
    cin >> N >> K;
    vector<long long int> H(N);
    for(long long int i=0;i<N;i++){
        cin >> H[i];
    }

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

    for(long long int i=0;i<N-K;i++){
        sum += H[i];
    }

    cout << sum << endl;
}

Measured memory_bytes: 1792
#include <stdio.h>
int main(int argc, char const *argv[])
{
    char str[11], temp[11];
    int cnt = 0;
    scanf("%s", str);

    for (int i = 0; i < 10; i++)
    {
        switch (str[i])
        {
        case '0':
            temp[cnt] = '0';
            cnt++;
            break;

        case '1':
            temp[cnt] = '1';
            cnt++;
            break;

        case 'B':
            if (cnt <= 0)
            {
                break;
            }

            cnt--;
            break;

        default:
            break;
        }
    }

    temp[cnt] = '\0';

    printf("%s\n", temp);

    return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}

ll d,start,end;

//辺の情報を個別に持つタイプ
typedef struct edge{ll s,g,c,f;}E;
typedef struct graph{
	int vcnt,ecnt;
	E  e[200010];//適宜変える(ecnt)
	int inv[200010];//逆辺のindex(ecnt)
	int id[100010];//適宜変える(vcnt)
}G;
G g;

int esort(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).s<(*q).s)return -1;
	if((*p).s>(*q).s)return  1;
	if((*p).g<(*q).g)return -1;
	return 1;
}
void makeinvedge();
void readgraph(){
	//適宜変える
	ll n;
	scanf("%lld%lld%lld%lld",&n,&d,&start,&end);
	start--,end--;
	rep(i,0,n-1){
		ll x,y,c;
		scanf("%lld%lld%lld",&x,&y,&c);
		x--,y--;
		g.e[2*i].s=x;
		g.e[2*i].g=y;
		g.e[2*i].c=c;
		g.e[2*i+1].s=y;
		g.e[2*i+1].g=x;
		g.e[2*i+1].c=c;
	}
	g.vcnt=n;
	g.ecnt=2*n-2;
	qsort(g.e,g.ecnt,sizeof(E),esort);
	makeinvedge();

	int p=0;
	rep(i,0,g.vcnt){
		while(p<g.ecnt&&g.e[p].s<i)p++;
		g.id[i]=p;
	}
	g.id[g.vcnt]=g.ecnt;//番兵
}

//*
void makeinvedge(){
	//idx
	rep(i,0,g.ecnt){
		int l=0,r=g.ecnt;
		while(r-l>1){
			int m=(l+r)/2;
			if(g.e[m].s<g.e[i].g||(g.e[m].s==g.e[i].g&&g.e[m].g<=g.e[i].s))l=m;
			else r=m;
		}
		g.inv[i]=l;
	}
}
//*/


//dfs
int oyav[100010];
int oyae[100010];
ll dfs1(int v,int pre){
	//S-Eパスを見つける
	int flag=v==end;
	oyav[v]=pre;
	rep(i,g.id[v],g.id[v+1]){
		if(g.e[i].g!=pre){
			int temp=dfs1(g.e[i].g,v);
			if(temp){
				g.e[i].f=1;
				g.e[g.inv[i]].f=1;
				flag=1;
			}
		}else{
			oyae[v]=i;
		}
	}
	return flag;
}
void dfs2(int v,int pre){
	//親と繋がる辺の耐久度を子の数だけ減らす
	int cnt=0;
	rep(i,g.id[v],g.id[v+1])if(g.e[i].g!=pre){
		dfs2(g.e[i].g,v);
		cnt++;
	}
	int oyaidx=oyae[v];
	if(pre!=-1&&!g.e[oyaidx].f){
		g.e[oyaidx].c-=d*cnt;
		g.e[g.inv[oyaidx]].c-=d*cnt;
	}
}

ll a[100010];
int f(int v){
	int cnt=0;
	int flag=-1;
	rep(i,g.id[v],g.id[v+1])if(oyav[v]!=g.e[i].g){
		if(g.e[i].f){
			flag=i;
		}else{
			a[cnt++]=g.e[i].c;
		}
	}
	sortup(a,cnt);
//	printf("%d %d:\n",v,oyav[v]);rep(i,0,cnt)printf("%d ",a[i]);puts("");
	rep(i,0,cnt)if(a[i]<=(i+1+(oyav[v]!=-1))*d)return 0;
	if(flag!=-1)return g.e[flag].c>(cnt+(oyav[v]!=-1))*d;
	return 1;
}

int main(){
	readgraph();
	dfs1(start,-1);
	dfs2(start,-1);
//	rep(i,0,g.ecnt)if(g.e[i].s<g.e[i].g)printf("%d %d %lld %d\n",g.e[i].s,g.e[i].g,g.e[i].c,g.e[i].f);
	rep(i,0,g.vcnt)if(!f(i)){
		puts("No");
		return 0;
	}
	puts("Yes");
}


Measured memory_bytes: 14160