akhauriyash/Code-Regression huggingface dataset:
/*
ID: arthurc4
TASK: test
LANG: C++11
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
#define REP(i, a, b) \
for (int i = int(a); i <= int(b); i++)
#define REPb(j, d, c) \
for (int j = int(d); j >= int(c); j--)
#define ff \
first
#define ss \
second
#define pb \
push_back

int main()
{
	//ifstream cin("input.txt");
	//ifstream cin("test.in");
	//ofstream cout("test.out");

	int n;
	cin>>n;

	vll dp(n+1);
	dp[0]=1;
	vi last_index(200001);
	vi prior_colour(200001);

	REP(i,1,n)
	{
		int c;
		cin>>c;
		prior_colour[i]=last_index[c];
		last_index[c]=i;
	}

	// REP(i,1,n)
	// {
	// 	cout << i << endl;
	// 	cout << prior_colour[i] << " " << last_index[i] << endl;
	// }

	REP(i,1,n)
	{
		dp[i]=dp[i-1];
		if(prior_colour[i] && prior_colour[i]!=i-1) dp[i]+=dp[prior_colour[i]];
		dp[i]%=(ll(1e9)+7);
		//cout << i << " " << dp[i] << endl;
	}

	cout << dp[n] << endl;

	return 0;
}

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

#define N 1005

using namespace std;

int ans;

template<typename Drake>
void read(Drake &x){
	x=0;char ch=getchar();bool f=1;
	while(!isdigit(ch)){
		if(ch=='-')f^=1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=(2*f-1);
}

template<typename Drake>
void write(Drake x){
	if(x<0){x=-x;putchar('-');}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

template<typename Drake>
void writeln(Drake x){
	write(x);
	puts("");
}

void init(){
	int a,b;
	ans=0;
	cin>>a>>b;
	ans=a;
	if(b<a)
	ans--;
}	

int main(){
	init();
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int n;
  double v[50];
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> v[i];
  }
  // 昇順ソート
  sort(v, v+n);
  // 小さい方から合成していく
  double ans = 0., tmp=0.;
  for(int i=1; i<n; i++){
    tmp = (v[i-1] + v[i]) /2.0;
    v[i] = tmp;
  }
  ans = v[n-1];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<algorithm>
#include<cmath>
#include<map>

using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){

    int K, X;

    cin >> K >> X;

    if(500 * K >= X) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}



Measured memory_bytes: 888
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define ll long long
#define double long double
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define ALL(V) ((V).begin(),(V).end())
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
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;}
using namespace std;

int main(){
  ll N,M,sum=0;
  cin>>N>>M;
  ll A[M];
  REP(i,M){
    cin>>A[i];
    sum+=A[i];
  }
  
  if(N<sum) cout<<-1<<endl;
  else cout<<N-sum<<endl;
}

Measured memory_bytes: 3644
#include <stdio.h>
#include <string.h>
int main(void){
    // Your code here!
    char s[200001],t[200001];
    scanf("%s",s);
    scanf("%s",t);
    int a[26],b[26],i;
    for(i=0;i<26;i++){
        a[i]=-1;
        b[i]=-1; 
    }
    int len=strlen(s);
    int f=1;
    for(i=0;i<len;i++){
        int x=s[i]-'a',y=t[i]-'a';
        if(a[x]==-1) a[x]=y;
        else if(a[x]!=y){
            f=0;
            break;
        }
        if(b[y]==-1) b[y]=x;
        else if(b[y]!=x){
            f=0;
            break;
        }
    }
    if(f) printf("Yes");
    else printf("No");
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(void){
  int d, n;
  cin >> d >> n;
  if(n != 100) cout << (int)pow(100, d) * n << endl;
  else cout << (int)pow(100, d) * (n+1) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
#include <math.h>
using namespace std;
#pragma warning(disable : 4996)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;


int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	vector<vector<int>> a(3, vector<int>(3, 0)), used(3, vector<int>(3, 0));
	for (int j = 0; j < 3; j++) {
		for (int k = 0; k < 3; k++) {
			cin >> a[j][k];
		}
	}
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (a[j][k] == x)used[j][k] = 1;
			}
		}
	}
	vector<int> s(8);
	for (int i = 0; i < 3; i++) {
		int c = used[i][0] + used[i][1] + used[i][2];
		s[i] = c;
	}
	for (int i = 0; i < 3; i++) {
		int c = used[0][i] + used[1][i] + used[2][i];
		s[i + 3] = c;
	}
	s[6] = used[0][0] + used[1][1] + used[2][2];
	s[7] = used[0][2] + used[1][1] + used[2][0];
	for (int i = 0; i < 8; i++) {
		if (s[i] == 3) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<int>>;
using dou =long double;
string Yes="Yes";
string YES="YES";
string NO="NO";
string No="No";
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; }
#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(int i = m; i < (int)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define res resize
#define as assign
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
 
typedef long long ll;
const int INF = 2000000000;
const ll INF64 = 922337203685477580ll;
const int mod = 1000000007ll;
const ll  MOD = 1000000007LL;


int main(){
    int n;
    std::cin >> n;
    VEC(int,a,2*n);
    sort(all(a));
    int ans=0;
    rep(i,n){
        ans+=a[i*2];
    }
    std::cout << ans << std::endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  int n,a,b;
  cin >> n >> a >> b;
  vector<int> m(n);
  for(int i = 0;i < n;i++)cin >> m[i];
  int x,y,z;
  x = 0;
  y = 0;
  z = 0;
  for(int i = 0;i < n;i++){
    if(m[i] <= a)x++;
    else if(m[i] >= b + 1)z++;
    else y++;
  }
  cout << min({x,y,z}) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+5;
inline int read(){
	char c=getchar();int t=0,f=1;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
	return t*f;
}
int n,l,a[maxn],mn=0x3f3f3f3f,sum;
int main(){
	n=read(),l=read();
	for(int i=1;i<=n;i++){a[i]=l+i-1;if(abs(a[i])<abs(mn))mn=a[i];sum+=a[i];}
	printf("%d\n",sum-mn);
	return 0;
}


Measured memory_bytes: 256
import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

MaxQ = 10**5+1
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

a = [0]*MaxQ
s = [0]*MaxQ
prime = isPrime_np(MaxQ)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
s = np.cumsum(a)
    
for l,r in lr:
    ans.append(s[r] - s[l-1])
print(*ans,sep="\n")   

Measured memory_bytes: 53456
#include <bits/stdc++.h>
#define int long long int
using namespace std;
template<typename T,typename U> using P=pair<T,U>;
template<typename T> using V=vector<T>;
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}

template<typename T>auto&operator<<(ostream&s,const vector<T>&v){s<<"[";bool a=1;for(auto e:v){s<<(a?"":" ")<<e;a=0;}s<<"]";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const pair<T,U>&p){s<<"("<<p.first<<","<<p.second<<")";return s;}
template<typename T>auto&operator<<(ostream&s,const set<T>&st){s<<"{";bool a=1;for(auto e:st){s<<(a?"":" ")<<e;a=0;}s<<"}";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const map<T,U>&m){s<<"{";bool a=1;for(auto e:m){s<<(a?"":" ")<<e.first<<":"<<e.second;a=0;}s<<"}";return s;}
#define DUMP(x)  cerr<<#x<<" = "<<(x)<<endl;

struct edge { int to, cost; };

const int INF = 1e18;
const int MOD = 1e9+7;

signed main()
{
   int n; cin >> n;
   V<int> a(n);
   for (int i = 0; i < n; i++) {
      cin >> a[i];
   }

   V<V<int>> dp(n+1, V<int>(2, -1));
   dp[0][0] = 0;
   for (int i = 0; i < n; i++) {
      if (a[i] % 2 == 0) {
         if (max(dp[i][0], dp[i][1]) != -1) {
            chmax(dp[i+1][0], max(dp[i][0], dp[i][1]) + a[i]/2);
         }
         if (a[i] == 0) {
            dp[i+1][1] = -1;
         } else if (dp[i][1] != -1) {
            chmax(dp[i+1][1], dp[i][1] + a[i]/2);
         }
      } else {
         if (max(dp[i][0], dp[i][1]) != -1) {
            chmax(dp[i+1][1], max(dp[i][0], dp[i][1]) + (a[i]-1)/2);
         }
         if (dp[i][1] != -1) {
            chmax(dp[i+1][0], dp[i][1] + (a[i]+1)/2);
         }
      }
   }
   cout << max(dp[n][0], dp[n][1]) << endl;

   return 0;
}


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

using namespace std;

int main() {
    string S;
    //string str;
    //int tmp = 0;
    int result = 0;

    cin >> S;

    //tmp = (int)(S[0]);
    //str = str + (char)(tmp);
    for(int i = 1; i < S.size(); i++) {
        if(S[i-1] == S[i]) {
            //cout << "***" << endl;
            
            result ++;
            if(S[i] == '0') {
                S[i] = '1';
            } else {
                S[i] = '0';
            }
        } else {
            //cout << "+++" << endl;
            //tmp = (int)(S[i]);
        }

        //str = str + (char)(tmp);
    }

    cout << result << endl;
    //cout << str << endl;
    
}

Measured memory_bytes: 512
#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 can_be_mm(const char a, const char b) {
    int x = a - '0';
    int y = b - '0';

    if (x >= 2) {
        return false;
    } else if (x == 1) {
        return y <= 2;
    } else {
        return y != 0;
    }
}

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

    bool is_yymm = false, is_mmyy = false;

    if (can_be_mm(S[2], S[3])) {
        is_yymm = true;
    }
    if (can_be_mm(S[0], S[1])) {
        is_mmyy = true;
    }

    if (is_yymm && is_mmyy) {
        cout << "AMBIGUOUS" << endl;
    } else if (is_yymm) {
        cout << "YYMM" << endl;
    } else if (is_mmyy) {
        cout << "MMYY" << endl;
    } else {
        cout << "NA" << endl;
    }

    return 0;
}


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

using namespace std;


int main()
{

     int a,b,c;
     cin>>a>>b>>c;

     if(a==5 && b==5 && c==7)
     cout<<"YES"<<endl;

     else if(a==5 && b==7 && c==5)
     cout<<"YES"<<endl;

     else if(a==7 && b==5 && c==5)
     cout<<"YES"<<endl;
     else
     cout<<"NO"<<endl;




}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn min<T: std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        return a;
    } else {
        return b;
    }
}

fn solve(s: String) -> usize {
    let si: Vec<char> = s.chars().collect();

    let mut dp = vec![vec![std::usize::MAX - 10; 2]; s.len()+1];
    dp[0][0] = 0;
    dp[0][1] = 1;

    for i in 0..s.len() {
        let D: usize = (si[i] as usize) - ('0' as usize);
        for j in 0..2 {
            let d = D + j;
            dp[i+1][j] = min(dp[i+1][j], dp[i][0] + d);
            dp[i+1][j] = min(dp[i+1][j], dp[i][1] + (10 - d));
        }
    }

    return dp[s.len()][0];
}

fn main() {
    let n: String = read();

    println!("{}", solve(n));
}


Measured memory_bytes: 49396
#include <iostream> 
#include <cstdio> 
#include <cstdlib>  
#include <algorithm> 
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include<iomanip>
#include<functional>
using namespace std;
typedef long long ll;


long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}


int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    ll ans = 0;
    ll a = 0, b = 0;
    for (int i = N - 1; i > 0; i--) {
        if (A[i] == A[i - 1]) {
            if (a) b = A[i];
            else a = A[i];
            i--;
        }
        ans = max(ans, a * b);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3692
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <map>

#define ll long long
#define REP(i,n) for(int i = 0; i < n; i++)
#define PI 3.141592653589
#define MOD 1000000007

using namespace std;

template<typename T> T gcd(T a, T b){return (a % b)? gcd(b, a % b) : b;}
template<typename T> T lcm(T a, T b){return a * b / gcd(a, b);}

void solve_A(){
    
    REP(i,5){
        int x;
        cin >> x;
        if(x == 0) cout << i + 1 << endl;
    }
}

void solve_B(){
    int x, y;
    cin >> x >> y;

    bool flag = false;
    if((y-2*x >= 0) && (y-2*x) % 2 == 0){
        if((4*x-y >= 0) && (4*x - y) % 2 == 0){
            flag = true;
        }
    }

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

void solve_C(){
    int x, n;
    cin >> x >> n;
    int ans = 1000000;
    int index = -1;
    vector<bool> number(105, true);
    REP(i,n){
        int p;
        cin >> p;
        number[p] = false;
    }

    for(int i = 103; i >= 0; i--){
        if(number[i]){
            if(fabs(x - i) <= ans){
                index = i;
                ans = fabs(x-i);
            }
        }
    }

    cout << index << endl;
}

int main(void){
    solve_C();
    
    return 0;
}

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

int main() {
  int k, n; cin >> k >> n;
  int tmp1; cin >> tmp1;
  int a = tmp1, b = 0;
  int sa = 0;
  for(int i = 1; i < n; i++){
    int tmp2; cin >> tmp2;
    if(tmp2 - tmp1 > sa) sa = tmp2 - tmp1;
    tmp1 = tmp2;
    if(i == n-1) b = tmp2;
  }
  if(k - b + a > sa) sa = k - b + a;
  cout << k - sa;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<string>
#include<numeric>
#include<sstream>
#include<cmath>
using namespace std;
int main(){

  int n, m, c; cin >> n >> m >> c;
  vector<int> b(m);
  for(int i=0; i<m; i++) cin >> b[i];
  vector< vector<int> > a(n, vector<int> (m));
  for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin >> a[i][j];

  int cnt = 0;
  for(int i=0; i<n; i++) {
    int x = c;
    for(int j=0; j<m; j++){
      x += a[i][j] * b[j];
    }
    if(x > 0) cnt++;
  }
  cout << cnt << endl;


  return 0;
}


//


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <regex> //正規表現
#include <map>
#include <set>
#include <cassert> //assart
using namespace std;
#define ll long long int
#define FOR(i,min,max) for(int i=(min);i<(max);i++)
#define FOReq(i,min,max) for(int i=(min);i<=(max);i++)
#define FORREV(i,max,min) for(int i=(max)-1;i>=(min);i--)
const int  MOD=1e9+7;
const int  INF=2000000000;
const int INF2=  10000000;
const double  Micro=1e-5;

int UnUsedVariable(){
    if(INF || Micro || MOD || INF2){;}
    return 0;
}

#define pf printf
#define sf scanf
#define inarray(array,min,max) FOR(i,min,max){cin>>array[i];}
#define inarrayW(arrayA,arrayB,min,max) FOR(i,min,max){cin>>arrayA[i]>>arrayB[i];}
inline int isEven(int x){return x%2==0;}
inline int isOdd (int x){return x%2==1;}
#define br printf("\n");
#define OutputAndReturn0(x) {cout<<(x)<<endl;return 0;}

int printintN(int array[],const int num){
    for(int i=0;i<num;i++){printf("%d ",array[i]);}
    br;
    return 0;
}


//#define int long long int

/*
 1.困った時こそ冷静に問題文を見直す！制約条件を見ろ！乱択アルゴリズムとかO(N^3)とか！
 2.一度に大量のことをやろうとしない。デバッグしやすいように細かく！
 3.プログラミングは半分数学だし、もう半分は数学ではない！
 4.できない問題はできない！！！！！
 */

int experiment(){
    int ans;ans=0;
    string s;cin>>s;
    int Size=(int)s.size();
    FOR(i, 0, Size){
        if(s[i]=='A' or s[i]=='C' or s[i]=='G' or s[i]=='T')s[i]='A';
    }
    int ALength=0;
    FOR(i, 0, Size){
        if(s[i]=='A')ALength++;else ALength=0;
        ans=max(ans,ALength);
    }
    OutputAndReturn0(ans);
    return 0;
}
signed main(){
    assert(1);
    experiment();
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

template <class T1, class T2>
ostream& operator << (ostream& out, const pair <T1, T2> p)
{
    out << '(' << p.first << ',' << p.second << ')';
    return out;
}

template <class T1, class T2>
istream& operator >> (istream& in, pair<T1, T2> &p)
{
    in >> p.first >> p.second;
    return in;
}

template <class T>
istream& operator >> (istream& in, vector<T> &v)
{
    for (T &x : v)
        in >> x;
    return in;
}

template <class T>
ostream& operator << (ostream& out, const vector<vector<T>> &v)
{
    for (const vector<T> &x : v)
        out << x << '\n';
    return out;
}

template <class T>
ostream& operator << (ostream& out, const vector<T> &v)
{
    for (const T &x : v)
        out << x << ' ';
    return out;
}

long long gcd (long long a, long long b)
{
    if (b > a)
        swap(a, b);
    return (b ? gcd(b, a % b) : a);
}

using ll   = long long;
using pii  = pair<int, int>;
using pll  = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi   = vector<int>;
using vl   = vector<long long>;
using vvi  = vector<vector<int>>;
using vvl  = vector<vector<long long>>;

#define F          first
#define S          second
#define First      first.first
#define Second     first.second
#define Third      second
#define mp         make_pair
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define per(i,b,a) for (int i = (b); i > (a); i--)
#define all(x)     x.begin(), x.end()
#define ret(x)     return cout << x, 0;
#define throwex    throw runtime_error ("Found the error.");

const int h = 1000000007;

namespace modexp
{
    const int mod = 1000000007;

    constexpr long long p (long long x, long long y)
    {
        long long ans = 1;
        while(y)
        {
            if(y & 1)
                (ans *= x) %= mod;
            (x *= x) %= mod;
            y /= 2;
        }
        return ans;
    }

    constexpr long long inv (const long long x)
    {
        return p (x, mod - 2);
    }
}
using modexp::p;
using modexp::inv;

signed main()
{
    ios::sync_with_stdio(false);
    #ifdef ONLINE_JUDGE
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.setstate(ios::failbit);
    #endif

    int n, m;
    cin >> n >> m;
    vvl dp(m+1, vl(n+1));
    rep(i,0,m+1)
        dp[i][0] = 1;
    rep(i,1,n+1)
        dp[0][i] = 1;
    rep(j,1,n+1)
    {
        ll x = 0;
        rep(i,1,m+1)
        {
            (dp[i][j] += dp[i][j-1] * (i + 1)) %= h;
            (x *= 2) %= h;
            (x += dp[i-1][j-1] * (i - 1)) %= h;
            (dp[i][j] += x) %= h;
        }
    }
    // cerr << dp << '\n';
    cout << dp.back().back();
}


Measured memory_bytes: 198656
using System;

namespace abc149B
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split();
            ulong A = ulong.Parse(str[0]);
            ulong B = ulong.Parse(str[1]);
            ulong K = ulong.Parse(str[2]);
            if (A >= K)
            {
                A = A - K;
                Console.WriteLine(A + " " + B);
            }
            else if (B >= (K - A))
            {
                B = B - (K - A);
                A = 0;
                Console.WriteLine(A + " " + B);
            }
            else
                Console.WriteLine(0 + " " + 0);
        }
    }
}


Measured memory_bytes: 11092
import sys
import heapq
#入力
n,k=map(int,input().split())
sushi=[[int(i) for i in l.split()] for l in sys.stdin]
#まずsushiを二番目の要素で降順にsort
sushi.sort(key=lambda x: x[1],reverse=True)
#次に大きい順からk個取ってきてsummationに加えると共に種類数を記録する
#この時にどの種類の寿司が加えられたかを記録しておき、二個目以降ではheapqにつっこむ
summation=0
various=0
stack=[0]*(n+1)
heap_min=[]
for i in range(k):
  if stack[sushi[i][0]]==0:
    stack[sushi[i][0]]=1
    various+=1
  else:
    heap_min.append(sushi[i][1])
  summation+=sushi[i][1]
#残ったものの中からまだ出てきていない種類の寿司の最大値をheapqにつっこむ
#このときすでにソートされているので、前からやっていってはじめに出てきたやつが最大値
heap_max=[]
for i in range(k,n):
  if stack[sushi[i][0]]==0:
    stack[sushi[i][0]]=1
    heap_max.append((-sushi[i][1],sushi[i][1]))
#heapify
heapq.heapify(heap_min)
heapq.heapify(heap_max)
#ansを計算していく
ans=summation+various*various
for i in range(1,k-various+1):
  if len(heap_min)==0 or len(heap_max)==0:
    break
  summation-=heapq.heappop(heap_min)
  summation+=heapq.heappop(heap_max)[1]
  ans=max(ans,summation+(various+i)*(various+i))
#出力
print(ans)

Measured memory_bytes: 27452
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説通りに実装したソースコード
 */
public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), k = scanner.nextInt();
			int[] a = new int[n];
			int max = IntStream.range(0, n).map(i -> a[i] = scanner.nextInt()).max().getAsInt();
			// left必ず達成できない、right必ず達成できる
			int left = 0, right = max;
			while (right - left > 0) {
				int mid = (left + right) / 2;
				if ((left == mid) || (right == mid)) {
					break;
				}
				if (ok(n, k, a, mid)) {
					right = mid;
				} else {
					left = mid;
				}
			}
			System.out.println(right);
		}
	}

	/**
	 * 目標値をk回まで切ることで達成できるかを計算する
	 * 
	 * @param n      丸太の数
	 * @param k      切る回数の上限
	 * @param a      丸太の長さの配列
	 * @param target 目標値
	 * @return 目標値をk回のカットで達成できるか
	 */
	private static boolean ok(int n, int k, int[] a, int target) {
		return IntStream.range(0, n).map(i -> (int) (((long) a[i] + target - 1) / target - 1)).sum() <= k;
	}
}


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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF             2e9
#define INF_LL          1LL<<60
#define ll              long long
#define Ceil(x, n)      (((((x))+((n)-1))/n))
#define CeilN(x, n)     (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)    ((x)-(x)%(n))
#define ALL(x)          (x).begin(),(x).end()
typedef pair<ll, ll>    P;

int main() {
    int n, k, c;
    cin >> n >> k >> c;
    string s;
    cin >> s;
    vector<int> l(k), r(k);
    int sa = INF;
    int idx = 0;

    /* 左から */
    REP(i, n) {
        if(idx == k) break;
        if(s[i] == 'x') {
            sa++;
            continue;
        }
        if(c <= sa) {
            sa = 0;
            l[idx] = i;
            idx++;
        } else {
            sa++;
        }
    }

    /* 右から */
    sa = INF, idx = 0;
    REP_REV(i, n) {
        if(idx == k) break;
        if(s[i] == 'x') {
            sa++; continue;
        }
        if(c <= sa) {
            sa = 0;
            r[idx] = i;
            idx++;
        } else {
            sa++;
        }
    }

    //REP(i, k) cout << l[i] << " " << r[k-1-i] << endl;

    REP(i, k) {
        if(l[i] == r[k-1-i]) cout << l[i] + 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 3332
N = int(input())
A = [int(input()) for i in range(N)]
tmp = 0
for i in range(N):
    if A[i] > A[tmp]:
        tmp = i
maxA = A[tmp]
answer = [maxA]*N
B = sorted(A)
A[tmp] = -float("inf")
C = sorted(A)
answer[tmp] = C[-1]

print(*answer, sep="\n")

Measured memory_bytes: 77016
program one
  implicit none
  integer :: i
  integer :: num, count

  read(*,*)num
  count=0
  do i=1,9
     if (i*1000<=num .and. num<(i+1)*1000) then
        num=num-i*1000
        if (i==2) then
           count=count+1
        end if
     end if
  end do
  do i=1,9
     if (i*100<=num .and. num<(i+1)*100) then
        num=num-i*100
        if (i==2) then
           count=count+1
        end if
     end if
  end do
  do i=1,9
     if (i*10<=num .and. num<(i+1)*10) then
        num=num-i*10
        if (i==2) then
           count=count+1
        end if
     end if
  end do
  if (num==2) then
     count=count+1
  end if

  write(*,*)count

end program one

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

int a[200001];
int main() {
    int n,k;
   
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        int nn;
        cin >> nn;
        a[nn]++;
    }
    vector<int> cnt;
    for(int i = 1; i<=n; i++) {
        if(a[i] == 0)continue;
        cnt.push_back(a[i]);
    }
    sort(cnt.begin(), cnt.end());
    int rem = cnt.size() - k;
    int nums = 0;
    for(int i = 0; i < rem; ++i) {
        nums += cnt[i];
    }
    cout << nums << endl;
    return 0;
}


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

const int MAX=100005;
int N;

int score[MAX],state[MAX];
vector<pair<int,int>> T[MAX];
stack<pair<int,int>> S;
bool DFS(){
    bool check=true;
    for(int i=0;i<N;i++){
            S.push(make_pair(i,score[i]));
            state[i]=1;
        while(S.size()){
            int a=S.top().first;
            int b=S.top().second;
            int j;
            for(j=0;j<T[a].size();j++){
                int c=T[a][j].first;
                int d=T[a][j].second;
                if(state[c]==0){
                    score[c]=b+d;
                    state[c]=1;
                    S.push(make_pair(c,score[c]));
                    break;
                }
                else if(state[c]==1){
                    if(score[c]!=b+d){
                        check=false;
                    }
                }
            }
            if(T[a].size()==0||j==T[a].size()) S.pop();
        }
    }
    return check;
    
}

int main(){
    
    int M;cin>>N>>M;
    for(int i=0;i<N;i++){
        state[i]=0;
        score[i]=0;
    }
    for(int i=0;i<M;i++){
        int a,b,c;cin>>a>>b>>c;
        a--;b--;
        T[a].push_back(make_pair(b,c));
        T[b].push_back(make_pair(a,-c));
    }
    for(int i=0;i<N;i++){
        sort(T[i].begin(),T[i].end());
    }
    if(DFS()) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}



Measured memory_bytes: 10112
n, k = map(int, input().split())
d = list(map(str, input().split()))
possible = [str(i) for i in range(10) if str(i) not in d]
for i in range(n,10**5):
    for j in str(i):
        if j not in possible:
            break
    else:
        print(i)
        exit()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define FOR(i, l, r) for(ll i = l; i < r; i++)
#define rep(i, N) FOR(i, 0, N)
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll MOD = round(1e9+7);


int main() {
    int N; cin >> N;
    vi a(N); rep(i,N) cin >> a[i];
    ll ans = 0;
    rep(i,N) ans += a[i]-1;
    
    //printf("%.15lf", ans);
    cout << ans <<"\n";
    return 0;
}


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

using namespace std;

int main()
{	
  
  int a,b;
  cin>>a>>b;
  
  if(a-2*b>0)
    cout<<a-2*b<<'\n';
  else
    cout<<0<<'\n';
  	
 
  return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter
import java.util.*

fun main(args: Array<String>) = IO().exec {
    val h = int()
    val w = int()
    val d = int()
    val a = Array(h){IntArray(w){int()-1}}
    val q = int()
    val l = IntArray(q)
    val r = IntArray(q)
    for (i in 0 until q) {
        l[i] = int()-1
        r[i] = int()-1
    }

    val reva = Array(h*w){Pair(0, 0)}
    for (y in a.indices) for (x in a[0].indices) reva[a[y][x]] = Pair(y, x)

    val ds = LongArray(h*w)
    for (i in d until h*w) ds[i] = ds[i-d] + cost(reva[i], reva[i-d])

    for (i in 0 until q) println(ds[r[i]] - ds[l[i]])
}

fun cost(p: Pair<Int, Int>, q: Pair<Int, Int>): Long =
        Math.abs(p.first-q.first).toLong() + Math.abs(p.second-q.second)

class IO {
    val printable = 33..126
    val buffer = ByteArray(1024)
    var ptr = 0
    var buflen = 0
    val out = PrintWriter(System.out)
    fun hasNextByte(): Boolean {
        if (ptr < buflen) {
            return true
        } else {
            ptr = 0
            buflen = System.`in`.read(buffer)
            if (buflen <= 0) {
                return false
            }
        }
        return true
    }
    fun readByte(): Byte {
        return if (hasNextByte()) buffer[ptr++] else return -1
    }
    fun hasNext(): Boolean {
        while (hasNextByte() && buffer[ptr] !in printable) ptr++
        return hasNextByte()
    }
    fun string(): String {
        if (!hasNext()) throw NoSuchElementException()
        val sb = StringBuilder()
        var b = readByte()
        while (b in printable) {
            sb.appendCodePoint(b.toInt())
            b = readByte()
        }
        return sb.toString()
    }
    fun long(): Long {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0L
        var minus = false
        var b = readByte()
        if (b == '-'.toByte()) {
            minus = true
            b = readByte()
        }
        if (b !in '0'.toByte()..'9'.toByte()) {
            throw NumberFormatException()
        }
        while (true) {
            if (b in '0'.toByte()..'9'.toByte()) {
                n *= 10
                n += b - '0'.toByte()
            } else if (b == (-1).toByte() || b !in printable) {
                return if (minus) -n else n
            } else {
                throw NumberFormatException()
            }
            b = readByte()
        }
    }
    fun int(): Int {
        val nl = long()
        if (nl !in Integer.MIN_VALUE..Integer.MAX_VALUE) throw NumberFormatException()
        return nl.toInt()
    }
    fun double(): Double {
        return string().toDouble()
    }
    fun print(obj: Any) = out.print(obj)
    fun print(i: Int) = out.print(i)
    fun print(l: Long) = out.print(l)
    fun println(obj: Any) = out.println(obj)
    fun println(i: Int) = out.println(i)
    fun println(l: Long) = out.println(l)
    inline fun exec(block: IO.() -> Unit) {
        block()
        out.flush()
    }
}

Measured memory_bytes: 45276
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (ll i = m; i < n; ++i)
#define FORR(i, m, n) for (ll i = m; i >= n; --i)
#define ALL(v) (v).begin(),(v).end()
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; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,a,b,c;cin >> n >> a >> b >> c;
    vector<int> l(n);
    REP(i,n){
        cin >> l[i];
    }
    int ans=inf;
    REP(i,1<<(n*2)){
        vector<int> d(n);
        int num=i,cnt=0;
        while(num){
            d[cnt]=num%4;
            num/=4;
            cnt++;
        }
        vector<int> p(3),q(3);
        REP(j,n){
            if(d[j]==1){
                p[0]+=l[j];
                q[0]++;
            }
            if(d[j]==2){
                p[1]+=l[j];
                q[1]++;
            }
            if(d[j]==3){
                p[2]+=l[j];
                q[2]++;
            }
        }
        if(q[0]==0||q[1]==0||q[2]==0){
            continue;
        }
        int res=abs(a-p[0])+abs(b-p[1])+abs(c-p[2])+10*(q[0]+q[1]+q[2]-3);
        chmin(ans,res);
    }
    cout << ans << endl;
}

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

using namespace std;

#define int long long
#define endl '\n'
#define MOD 1000000007
#define maxn 100010

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

    int n;
    cin >> n;

    vector<int> v(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        cin >> v[i];
    }
    vector<int> dp(n, 0);
    dp[0] = v[0];
    for (int i = 0; i < n - 1; i++) {
        if (dp[i] > v[i]) {
            dp[i] = v[i];
            dp[i + 1] = v[i];
        } else
            dp[i + 1] = v[i];
    }
    int ans = 0;
    for (auto x:dp)
        ans += x;
    cout << ans << endl;
    return 0;
}

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

  int main(){
      int n,k; 
      cin >> n >> k;
      int ans = 0;
      rep(i,n){
        int tmp;
        cin >> tmp;
        ans += min(abs(k-tmp),tmp)*2; 
      }
      cout << ans << endl;
}


Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
MAX = 10 ** 100

if n==0:
    print(1 if A[0] == 1 else - 1)
    exit()

if A[0] != 0:
    print(-1)
    exit()


# ok[i] : 深さiの葉以外の頂点の最大数
ok = [1]
for i in range(1, n + 1):
    t = ok[i - 1] * 2 - A[i]
    if i < n and t <= 0:
        print(-1)
        exit()
    ok.append(min(t, MAX))

if ok[n] < 0:
    print(-1)
    exit()

ans = [0] * (n + 1)

ans[n] = A[n]
# 深さ[親]の許容範囲を超えないように、できるだけたくさん親を使う
for i in range(n, 0, -1):
    ans[i - 1] = min(ok[i - 1], ans[i]) + A[i - 1]
# ans[上] = min(ok[上]*2, (ans[今]+A[今]))//2

print(sum(ans))

# print(ok)
# print(ans)


Measured memory_bytes: 20544
import numpy as np

N, k = list(map(int, input().split()))
if k > N:
    k = N
hs = list(map(int, input().split()))
hs = np.array([0] + hs)

# init
dp = np.zeros(N + 1).astype(int)
dp[2] = abs(hs[2] - hs[1])

# loop
if N > 2:
    for i in range(3, N + 1):
        """
        for j in range(1, k + 1):
            if i <= j:
                continue
            if dp[i] == 0:
                dp[i] = dp[i-j] + abs(hs[i] - hs[i-j])
            else:
                dp[i] = min(dp[i-j] + abs(hs[i] - hs[i-j]), dp[i])
        """
        x = max(1, i - k)
        dp[i] = np.min(dp[x:i] + np.abs(hs[i] - hs[x:i]))

# output
print(dp[N])

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

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<LL, LL>
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 2e5 + 10;
const int INF = 1e9 + 10;
int vis[26];
char st[qq];
int pos[qq];
int nxt[qq][26], A[26];

int main(){
	scanf("%s", st + 1);
	int n = strlen(st + 1);
	int cnt = 0, len = 1;
	pos[0] = n + 1;
	for(int i = n; i >= 1; --i) {
		if(!vis[st[i] - 'a']) {
			vis[st[i] - 'a'] = 1, cnt++;
		}
		if(cnt == 26) {
			cnt = 0, pos[len++] = i;
			mst(vis, 0);
		}
	}
	mst(vis, 0);
	//printf("QQQ\n");
	for(int i = 1; i < pos[len - 1]; ++i) {
		vis[st[i] - 'a'] = 1;
	}
//	printf("QQQ\n");
	char ch;
	for(int i = 0; i < 26; ++i) {
		if(!vis[i]) {
			printf("%c", ch = i + 'a');
			break;
		}
	}
//	printf("QQQ\n");
	for(int i = len - 1; i >= 1; --i) {
		int j;	mst(vis, 0);
		for(j = pos[i]; j < pos[i - 1]; ++j) {
			if(st[j] == ch) break;
		}
		for(j++; j < pos[i - 1]; ++j) {
			vis[st[j] - 'a'] = 1;
		}
		for(j = 0; j < 26; ++j) {
			if(!vis[j]) {
				printf("%c", ch = j + 'a');
				break;
			}
		}
	}
	puts("");
	return 0;
}

Measured memory_bytes: 2560
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
		int b = scanner.nextInt();
		int d = 0; int r = 0;
		double f = 0;
		d = a / b;
		r = a % b;
		double aa = (double)a;
		double bb = (double)b;
		f = aa / bb;
		System.out.printf (d +" "+ r +" " + "%.5f",f);
	}
}


Measured memory_bytes: 26544
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	string s;
	cin >> s;
	int l;
	l = s.size();
	int sum = l - 2;
	cout << s[0] << sum << s[l - 1] << endl;
	return 0;
}

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

signed main(){
  int N;
  cin>>N;
  vector<int> D(N);
  rep(i,N)cin>>D[i];
  sort(begin(D),end(D));
  int ans=1;
  rep(i,N-1){
    if(D[i+1]!=D[i])ans+=1;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3632
open Printf open Scanf
open Array

let () = scanf " %d %d" @@ fun n m ->
  let a = init n (fun _ -> scanf " %d %d" @@ fun u v -> u,v) in
  sort compare a;
  fold_left (fun (sum,left) (v,k) ->
    if k >= left then (
      print_int @@ sum + v * left; exit 0
    ) else (
      (sum+v*k,left-k)
    )
  ) (0,m) a |> ignore

Measured memory_bytes: 6784
import heapq

def main():
    N, K = map(int, input().split())
    sushi_list = []
    for _ in range(N):
        t, d = map(int, input().split())
        sushi_list.append((d,t))
    sushi_list = sorted(sushi_list, reverse=True)

    # 各種類(最大でK種類目まで)でおいしさが最大のものを保存
    keep = []
    # 取り替えるようのheapq
    exchange = []
    # keepに入っている種類
    types = set()
    for i in range(K):
        d, t = sushi_list[i]
        if t not in types:
            keep.append(d)
            types.add(t)
        else:
            heapq.heappush(exchange, d)

    base_point1 = sum(keep)
    base_point2 = sum(exchange)
    bonus_point = len(types)

    ans = base_point1 + base_point2 + bonus_point ** 2
    
    # K～N番目までをみて、選んでいない種類で最大のものを交換していく
    for i in range(K, N):
        if len(exchange) == 0:
            break

        d, t = sushi_list[i]
        # すでに選んだ種類のものはスキップする
        if t in types:
            continue 
        types.add(t)
        # 選んでいない種類で最大のものを追加する
        base_point1 += d
        # 選んだ種類で最小のものを削除する
        base_point2 -= heapq.heappop(exchange)
        bonus_point += 1
        ans = max(ans, base_point1 + base_point2 + bonus_point ** 2)

    print(ans)


    

main()

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

using namespace std;

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


const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()

int main(){
    int N,ANS=0;
    cin>>N;
    vector<int>P(N);
    rep(i,N)cin>>P[i];
    int cur=INF;
    rep(i,N){
        if(cur>P[i]){
            cur=P[i];
            ANS++;
        }
    }

    cout<<ANS<<endl;

    return 0;
}

//a=97,z=122

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

using namespace std;

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

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

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

    for (int i = 0; i < M; i++) {
        int discounted = A.back() / 2;
        A.pop_back();

        auto it = lower_bound(A.begin(), A.end(), discounted);
        A.insert(it, discounted);
    }

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        ans += A[i];
    }

    cout << ans << endl;
}

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

using namespace std;
using llint = long long;

int n, m, ans=0;
vector<int> k;
vector<int> p;

int main() {
    // Input
    cin >> n >> m;

    k.resize(m);
    vector<vector<int> > s(m);
    
    for (int i = 0; i < m; ++i) {
        cin >> k.at(i);
        s.at(i).resize(k.at(i));
    
        for (int j = 0; j < k.at(i); ++j) {
            cin >> s.at(i).at(j);
            --s.at(i).at(j);
        }
    }

    p.resize(m);
    for (int i = 0; i < m; ++i) {
        cin >> p.at(i);
    }

    // Solve
    for (int bit = 0; bit < (1<<n); ++bit) 
    {
        bool is_ans=true;

        for (int i = 0; i < m; ++i) {
            int sum = 0; 
            
            for (auto cs : s.at(i)) {
                if (bit >> cs & 1) {
                   ++sum;
                }
             }

             if (sum%2!=p.at(i))
             {
                 is_ans=false;
                 break;
             }
        }

        if (is_ans)
        {
            ans++;
        }
    }

    // Output
    cout << ans << endl;

    return 0;
}

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

int main(void){
    int l,r,d,one_to_r,one_to_l;
    cin >> l >> r >> d;

    one_to_r = r / d;
    one_to_l = (l - 1) / d;

    cout << one_to_r - one_to_l << endl;
    return 0;
}


Measured memory_bytes: 3632
n,m=map(int,input().split())
if m==0:
    print(10**(n-1) if n>1 else 0)
    exit()
d={}
for _ in range(m):
    s,c=map(int,input().split())
    s-=1
    if s==0 and c==0:
        if n==1:
            print(0)
            exit()
        print(-1)
        exit()
    if s in d and d[s]!=c:
        print(-1)
        exit()
    else:
        d[s]=c
l=["0"]*n
for i,k in d.items():
    l[i]=str(k)
if l[0]=="0":
    l[0]="1"
print("".join(l))


Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using node = tuple<int,int,int>;
const int inf = numeric_limits<int>::max()/3;

int state[15];
int dist[15];

int dfs(int now,int k){
  if(now == k)
    return 0;
  if(state[now] == dist[now]){
    return dfs(now+1,k);
  }
  int diff = (dist[now] - state[now] + 10) % 10;
  int res = inf;
  for(int i = now;i < k;++i){
    for(int j = now;j <= i;++j){
      state[j] = (state[j] + diff) % 10;
    }
    res = min(dfs(now+1,k)+1,res);
    for(int j = now;j <= i;++j){
      state[j] = (state[j] - diff + 10) % 10;
    }
  }
  return res;
}

void solve(int k){
  string s1,s2;
  cin >> s1 >> s2;
  for(int i = 0;i < k;++i)
    state[i] = s1[i] - '0';
  for(int i = 0;i < k;++i)
    dist[i] = s2[i] - '0';
  cout << dfs(0,k) << endl;
}

int main(void){
  int k;
  while(cin >> k,k)solve(k);
  return 0;
}

Measured memory_bytes: 2944
gets
x = gets.split(" ").map(&:to_f)
y = gets.split(" ").map(&:to_f)
d = [x,y].transpose.map{|c| c.inject(:-).abs}
(1..3).each do |i|
  puts (d.map{|c| c**(i)}.inject(:+)**(1.0/i)).round(6)
end
puts d.max

Measured memory_bytes: 8736
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define MAX_N 100000
#define MAX_P 200005
ll fact[MAX_P];
ll extgcd(ll a,ll b,ll& x,ll& y){
  ll d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
ll mod_inverse(ll a,ll m){
  ll x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
#define MAX_D 2222
ll dp[MAX_D][MAX_D];
int main(){
  ll n,d,x;
  while(cin>>n>>d>>x,n||d||x){
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    ll p=1,ans=0;
    for(int i=0;i<min(d,n);i++){
      ll sum[MAX_D];
      memset(sum,0,sizeof(sum));
      for(int j=0;j<n;j++) sum[j+1]=(sum[j]+dp[i][j])%MOD;
      for(int k=1;k<=n;k++){
	dp[i+1][k]+=(MOD+sum[k]-sum[max(0LL,k-x+1)])%MOD;
	dp[i+1][k]%=MOD;
      }
      p*=(d-i)%MOD;
      p%=MOD;
      p*=mod_inverse(i+1,MOD);
      p%=MOD;
      ans+=dp[i+1][n]*p;
      ans%=MOD;
    }
    /*//
    for(int i=0;i<=n;i++)
      for(int j=0;j<=n;j++)
	cout<<dp[i][j]<<" \n"[j==n];
    //*/
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 41664
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 100011

int n, c, k, i, j, ans;
int t[maxN];

bool check(int a, int b) {
    if (b > n) return false;
    if (b - a + 1 > c) return false;
    if (t[b] - t[a] > k) return false;
    return true;
}

int main()
{
  //  freopen("test.in","r",stdin);

    scanf("%d%d%d", &n, &c, &k);
    for (i = 1; i <= n; i++) scanf("%d", &t[i]);
    sort(t + 1, t + n + 1);

    for (i = 1; i <= n; i = j) {
        for (j = i; check(i, j); j++);
        ans++;
    }

    printf("%d", ans);


    return 0;
}


Measured memory_bytes: 640