akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  int n = 5;
  VEC<int> A(n, 0);
  VEC<int> B(n, 0);
  VEC<int> C(n, 0);
  REP(i, 0, n) {
    cin >> A[i];
    B[i] = A[i];
    C[i]=0;
    if (A[i] % 10 != 0) {
      B[i] += 10 - A[i] % 10;
      C[i]=10-A[i]%10;
    }
  }
  sort(ALL(C));
  reverse(ALL(C));
  LL sum =0;
  REP(i,0,n){
    sum+=B[i];
  }
  sum-=C[0];
  cout<<sum<<endl;
  

  return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

    Int N, M; cin >> N >> M;
    vector<string> A(N), B(M);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) cin >> B[i];

    rep(si, 0, N-M+1) {
        rep(sj, 0, N-M+1) {
            bool matched = true;
            rep(i, 0, M) {
                rep(j, 0, M) {
                    if (A[si+i][sj+j] != B[i][j]) matched = false;
                }
            }
            if (matched) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
}


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

#define ll long long
#define INF 1<<31-1
#define LNF 9223372036854775807
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
//#define MOD 998244353
#define NUM 200010
 
void swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
int abs(int a){if(a<0)return -a;return a;}
int dup(int a,int d){if(a%d==0)return a/d;else return a/d+1;}
int mod(int a,int m){if(a<0)return a%m+m;else return a%m;}

void swapl(ll* a,ll* b){ll tmp=*a;*a=*b;*b=tmp;}
ll absl(ll a){if(a<0)return -a;return a;}
ll dupl(ll a,ll d){if(a%d==0)return a/d;else return a/d+1;}
ll modl(ll a,ll m){if(a<0)return a%m+m;else return a%m;}

ll GCD(ll a,ll b){ll c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
ll LCM(ll a,ll b){return a*b/GCD(a,b);}

ll factorial(ll n, ll m) {return n < m ? 1 : n*factorial(n-1, m);}

int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(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);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

// ll dp[]
ll check[100001];

int main(){
    ll n, m;
    ll h[100001];
    ll a, b, ans=0;
    

    scanf("%lld%lld", &n, &m);

    for (int i = 0; i < n; i++)
    {
        scanf("%lld", h+i);
    }
    

    for (int i = 0; i < m; i++)
    {
        scanf("%lld%lld", &a, &b);
        if(h[a-1] == h[b-1]){
            check[a-1]++;
            check[b-1]++;
        }
        else if (h[a-1] > h[b-1])
        {
            check[b-1]++;
        }else if(h[b-1] > h[a-1]){
            check[a-1]++;
        }
    }
    
    for (int i = 0; i < n; i++)
    {
        if(check[i] == 0) ans++;
    }
    
    
    
    printf("%lld\n", ans);

  return 0;
}

Measured memory_bytes: 3280
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
using namespace std;

#define MOD 1000000007
#define p(x) cout << x << endl;
#define el cout << endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

    char x[3];
    cin >> x;

    if(x[0] == x[2]){
        p("Yes");
    }else{
        p("No");
    }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define HUGE_NUM 9999999999999999

struct Info{
	Info(int arg_to,ll arg_time,ll arg_cost,ll arg_min_rain){
		to = arg_to;
		time = arg_time;
		cost = arg_cost;
		min_rain = arg_min_rain;
	}
	int to;
	ll time,cost,min_rain;
};

struct Data{
	Data(int arg_node_id,int arg_pre_node,int arg_pre_id,ll arg_current_time,ll arg_rain_time){
		node_id = arg_node_id;
		pre_node = arg_pre_node;
		pre_id = arg_pre_id;
		current_time = arg_current_time;
		rain_time = arg_rain_time;
	}
	bool operator<(const struct Data &arg) const{
		return rain_time > arg.rain_time;
	}
	int node_id,pre_node,pre_id;
	ll current_time,rain_time;
};

int N,M,start,goal;
vector<Info> G[100000];

int main(){

	scanf("%d %d %d %d",&N,&M,&start,&goal);
	start--;
	goal--;

	int from,to;
	ll time,cost;

	for(int loop = 0; loop < M; loop++){
		scanf("%d %d %lld %lld",&from,&to,&time,&cost);
		from--;
		to--;
		G[from].push_back(Info(to,time,cost,HUGE_NUM));
	}

	priority_queue<Data> Q;
	for(int i = 0; i < G[start].size(); i++){
		G[start][i].min_rain = G[start][i].time;
		Q.push(Data(G[start][i].to,start,i,G[start][i].time+G[start][i].cost,G[start][i].time));
	}

	while(!Q.empty()){

		if(Q.top().node_id == goal){
			printf("%lld\n",Q.top().rain_time);
			return 0;
		}else if(Q.top().rain_time > G[Q.top().pre_node][Q.top().pre_id].min_rain){
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){
				if(Q.top().current_time > G[Q.top().node_id][i].time)continue;
				if(Q.top().rain_time+G[Q.top().node_id][i].time-Q.top().current_time >= G[Q.top().node_id][i].min_rain)continue;

				G[Q.top().node_id][i].min_rain = Q.top().rain_time+G[Q.top().node_id][i].time-Q.top().current_time;
				Q.push(Data(G[Q.top().node_id][i].to,Q.top().node_id,i,G[Q.top().node_id][i].time+G[Q.top().node_id][i].cost,G[Q.top().node_id][i].min_rain));
			}
			Q.pop();
		}
	}

	return 0;
}



Measured memory_bytes: 17596
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    int n,m,sum=0;
    cin>>n;
    vector<int>v;
    for(int i=0;i<n;i++)
    {
        cin>>m;
        v.push_back(m);
        sum+=m;
    }
    sort(v.begin(),v.end());
    if(sum-v[v.size()-1]>v[v.size()-1])
    {
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	
	int a,b;
	int h,m,s;
	int S;
	
	scanf("%d\n",&S);
	
	h = S / 3600;
	a = S % 3600;
	
	m = a / 60;
	b = a % 60;
	
	s = b;
	
	
	printf("%d:%d:%d\n",h,m,s);
	

	return 0;
	
}

Measured memory_bytes: 596
N = int(input())
S = input()
before_slime = S[0]
slime_num = 0 if len(S) > 1 else 1
same_flg = False
for i, slime in enumerate(S[1:]):
    if before_slime == slime and i == len(S[1:])-1:
        slime_num += 1
    elif before_slime != slime and i == len(S[1:])-1:
        slime_num += 2
    elif before_slime == slime and same_flg:
        before_slime = slime
    elif before_slime != slime and same_flg:
        slime_num += 1
        before_slime = slime
        same_flg = False
    elif before_slime == slime:
        before_slime = slime
        same_flg = True
    else:
        slime_num += 1
        before_slime = slime
print(slime_num)

Measured memory_bytes: 3444
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
    	Scanner scan=new Scanner(System.in);
    	String str=scan.next();
    	int C=-1;
    	int F=-1;
    	for(int i=0;i!=str.length();i++) {
    		if(str.charAt(i)=='C') {
    			C=i;
    		}if(str.charAt(i)=='F') {
    			F=i;
    		}
    	}
    	if(C!=-1&&F!=-1&&C<F) {
    		System.out.println("Yes");
    	}
    	else {
    		System.out.println("No");
    	}
    }
}

Measured memory_bytes: 21716
//This disgusting code is wriiten by Juruo D0zingbear
//Please don't hack me! 0v0 <3
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#define LL long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piii pair<int, pii >
#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define vi vector<int>
#define vpi vector< pii >
#define INF 2147483647
#define big 19260817
#define pb push_back
#define mp make_pair
using namespace std;
const int Maxk=1005;
string mul(string a,string b){
	int res[Maxk];
	memset(res,0,sizeof(res));
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for (int i=0;i<a.length();i++){
		for (int j=0;j<b.length();j++){
			res[i+j]+=(a[i]-'0')*(b[j]-'0');
		}
	}
	for (int i=0;i<Maxk;i++){
		if (res[i]>=10) {
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	string ret;
	bool flag=false;
	for (int i=Maxk-1;i>=0;i--){
		if (flag || res[i]){
			flag=true;
			ret=ret+(char)(res[i]+'0');
		}
	}
	if (ret=="") ret="0";
	return ret;
}
string add(string a,string b){
	if (a.length()<b.length()) swap(a,b);
	while (a.length()!=b.length()){
		b='0'+b;
	}
	for (int i=a.length()-1;i>=0;i--){
		a[i]+=(b[i]-'0');
		if (a[i]>'9' && i){
			a[i]-=10;
			a[i-1]++;
		}
	}
	if (a[0]>'9'){
		a[0]-=10;
		a='1'+a;
	}
	return a;
}

// cf IO: I64d
// atcoder IO: ｌｌｄ
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int Maxn=100005;
int a[Maxn];
int cnt[Maxn];
int main(){
	int n;
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
		if (a[i]) cnt[a[i]-1]++;
		cnt[a[i]+1]++;
	}
	int ans=0;
	for (int i=0;i<Maxn;i++){
		ans=max(ans,cnt[i]);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 1024
N = int( input() )
A = list( map( int, input().split() ) )
M = [ 0 ] * N
ALL = sum( A ) // 2

ng = 2
pl = N - 1
S = sum( [ A[ i ] for i in range( ng, pl + 1, 2 ) ] )
for i in range( 1, N // 2 + 1 ):
  M[ 2 * i - 1 ] = 2 * ( ALL - S )
  pl = ( pl + 2 ) % N
  S += A[ pl ] - A[ ng ]
  ng = ( ng + 2 ) % N

ng = 1
pl = N - 2
S = sum( [ A[ i ] for i in range( ng, pl + 1, 2 ) ] )
for i in range( N // 2 + 1 ):
  M[ 2 * i ] = 2 * ( ALL - S )
  pl = ( pl + 2 ) % N
  S += A[ pl ] - A[ ng ]
  ng = ( ng + 2 ) % N

ret = ""
for i in M:
  ret += str( i ) + " "
print( ret[ : - 1 ])


Measured memory_bytes: 15660
def find(x):
    if root[x] == x:
        return x
    else:
        root[x] = find(root[x])
        return root[x]

def same(x,y):
    return find(x) == find(y)

def unite(x,y):
    x = find(x)
    y = find(y)
    if rank[x] == rank[y]:
        root[y] = x
        rank[x] += 1
    elif rank[x] > rank[y]:
        root[y] = x
    elif rank[x] < rank[y]:
        root[x] = y
    
n,m = map(int, input().split())
root = [i for i in range(n)]
rank = [0 for i in range(n)]

for i in range(m):
    x, y, z = [int(i)-1 for i in input().split()]
    if not same(x,y):
        unite(x,y)
    
for i in range(n):
    find(i)

print(len(list(set(root))))


Measured memory_bytes: 13984
import math


def combination(i: int, j: int) -> int:
    return math.factorial(i) // math.factorial(i - j) // math.factorial(j)


if __name__ == "__main__":
    n, k = map(lambda x: int(x), input().split())
    modulo = 10 ** 9 + 7
    ans = 0
    if k <= n:
        for i in range(k):
            if 0 == i % 2:
                ans += (k - i) ** n * combination(k, i)
            else:
                ans -= (k - i) ** n * combination(k, i)
        ans = (ans // math.factorial(k)) % modulo

    print(ans)



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

typedef long long ll;

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

  ll n, m; cin >> n >> m;

  if((n+m)%2 == 1) {
    cout << "IMPOSSIBLE" << '\n';
    return 0;
  }
  cout << (n+m)/2 << '\n';
  return 0;
}


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

int main()
{
    int N;
    cin >> N;
    vector<string> S(N);
    vector<int> T(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> S[i] >> T[i];
    }
    string X;
    cin >> X;
    int index = 0;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == X)
        {
            index = i + 1;
            break;
        }
    }
    cout << accumulate(T.begin() + index, T.end(), 0) << endl;

    return 0;
}

Measured memory_bytes: 256
import collections
n=int(input())
s=input()
c=collections.Counter(s)
ans=c["R"]*c["G"]*c["B"]
for i in range(1,(n-1)//2+1):
  for k in range(n-i*2):
    if s[k]!=s[k+i] and s[k]!=s[k+2*i] and s[k+i]!=s[k+2*i]:
      ans-=1
print(ans)

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

int main() {
    int stayDays(0), Border(0), basicPayment(0), optionalPayment(0);
    cin >> stayDays >> Border >> basicPayment >> optionalPayment;

    int Sum(0);
    for(int i(0); i < stayDays; i += 1) {
        if(i < Border) Sum += basicPayment;
        else Sum += optionalPayment;
    }

    cout << Sum << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int n,A[MAX],B[MAX],k;

void CountingSort();

int main(){

  int i, j;

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

  }
 

  CountingSort();
  for(i=1;i<n+1;i++){
    if(i>1)printf(" ");
    printf("%d",B[i]);
  }
printf("\n");

  return 0;
}

void CountingSort()
{
  int i,j,C[VMAX];
  
  for(i=0;i<=VMAX;i++){
    C[i]=0;
  }
    
  for(j=1;j<=n;j++){
    C[A[j]]++;
  }

  for(i=1;i<=VMAX;i++){
    C[i]=C[i]+C[i-1];
  }

  for(j=n;j>=1;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
}



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

int main(){

    ll H, W;
    cin >> H >> W;

    ll h_num = 0;
    ll ans = 0;
    if (H%2 == 0) {
        h_num = H/2;
        ans = h_num*W;
    }
    else {
        h_num = H/2+1;
        for (ll i=0; i<W; i++){
            if (i%2 == 0){
                ans += h_num;
            }
            else{
                ans += h_num - 1;
            }
        }
    }

    if ((H == 1) || (W == 1)) cout << 1 << endl;
    else cout << ans << endl;
    return 0;
}


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

int main(){
  string a;
  cin >>a;
  int counter = 0;
  vector<int> c;
  for(char x:a){
   if(x == 'A' || x == 'T' || x == 'C' || x == 'G'){
     counter++;
     if(x == a[a.size() -1])
       c.push_back(counter);
   }else{
     c.push_back(counter);
     counter = 0;
   }
  }
  int maxv = 0;
  for(int x:c){
    maxv = max(maxv, x);
  }
  cout << maxv << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define pb push_back
#define pc __builtin_popcount
#define pcll __builtin_popcountll
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
using namespace std;
ll k, n, ans, a[500005];
int main() {
  speed;
  oprecision;
  // code
  cin >> k >> n;
  forn(n) cin >> a[i];
  for (int i = 1; i < n; i++) ans = max(ans, a[i + 1] - a[i]);
  cout << k - max(ans, a[1] + k - a[n]);
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

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

struct str{
    int a;
    int b;
    int c;
};

int main (void)
{
    int n;
    struct str s[10000];
    int i;
    scanf("%d",&n);

    for(i=0; i<n; i++){
        scanf("%d",&s[i].a);
        scanf("%d",&s[i].b);
        scanf("%d",&s[i].c);
    }

    for(i=0; i<n; i++){
        if(pow((double)s[i].a,2) + (double)pow(s[i].b,2) == (double)pow(s[i].c,2) || 
        pow((double)s[i].b,2) + pow((double)s[i].c,2) == pow((double)s[i].a,2) ||
        pow((double)s[i].c,2) + pow((double)s[i].a,2) == pow((double)s[i].b,2))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;


}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;

vector<ll> h(110000, 0);
vector<ll> dp(110000, INF);

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

  for(int i = 0; i < N; i++){
    cin >> h.at(i);
  }

  dp.at(0) = 0;

  for(int i = 0; i < N; i++){
    for(int j = 1; j <= K; j++){
      chmin(dp.at(i+j), dp.at(i) + abs(h.at(i+j) - h.at(i)));
    }
  }
  cout << dp.at(N-1) << endl;
}


Measured memory_bytes: 1920
H,W = map(int,input().split())
#print(H)
ans = 1
 
 
if H*W%2 == 0:
    ans = int(H*W/2)
else:
    ans = int(H*W//2 + 1)
#output
if H == 1:
    ans = 1
if W == 1:
    ans = 1
print(ans)

Measured memory_bytes: 2940
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)

max_num=max(a)
middle_num=max_num/2
num=0

for i in range(n):
    if a[i]> middle_num:
        num=i
        break

if middle_num-a[num-1]<=-middle_num+a[num]:
    print("{} {}".format(max_num,a[num-1]))
else:
    print("{} {}".format(max_num,a[num]))

Measured memory_bytes: 14420
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N=10005;
int dis[105][105];char ch[105][105];
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
int H,W;
void bfs(){
	for(int i=1;i<=H;++i)
		for(int j=1;j<=W;++j)
			dis[i][j]=114514;
	deque< pair<int,int> > q;
	dis[1][1]=(ch[1][1]=='#'?1:0);
	q.push_back(make_pair(1,1));
	while(!q.empty()){
		int x=q.front().fi,y=q.front().se,tmp;q.pop_front();
		if(y+1<=W){
			tmp=(ch[x][y]=='.' && ch[x][y+1]=='#');
			if(dis[x][y+1] > dis[x][y] + tmp){
				dis[x][y+1]=dis[x][y]+tmp;
				if(tmp) q.push_back(make_pair(x,y+1));
				else q.push_front(make_pair(x,y+1));
			} 
		} 
		if(x+1<=H){
			tmp=(ch[x][y]=='.' && ch[x+1][y]=='#');
			if(dis[x+1][y] > dis[x][y] + tmp){
				dis[x+1][y]=dis[x][y]+tmp;
				if(tmp) q.push_back(make_pair(x+1,y));
				else q.push_front(make_pair(x+1,y));
			}
		}
	}
}
int main(){
	cin>>H>>W;
	for(int i=1;i<=H;++i)
		for(int j=1;j<=W;++j)
			cin>>ch[i][j];
	bfs();
	cout<<dis[H][W];
	return 0;
}


Measured memory_bytes: 3652
#!/usr/bin/env python3

def abs_list_sum(numbers):
    result = 0
    for v in numbers:
        result += abs(v)
    return result


def abs_min(numbers):
    result = abs(numbers[0])
    for v in numbers:
        if result > abs(v):
            result = abs(v)
    return result

def main():
    n = int(input())
    a = list(map(int, input().split()))
    # count negative
    negative_count = 0
    for v in a:
        if v < 0:
            negative_count += 1
    if negative_count % 2 == 0:
        print(abs_list_sum(a))
    else:
        minimum = abs_min(a)
        print(abs_list_sum(a) - 2 * minimum)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14468
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    string s;
    cin >> s;
    ll n = s.size();

    vvl dp(n+1, vl(13));  // dp[i+1][j] : 先頭i文字(iは0-index)で13で割った余りがjとなるものの数
    dp[0][0] = 1;
    rep(i, n) {
        rep(j, 13) {
            if(s[i] == '?') {
                rep(x, 10) {
                    dp[i+1][(10*j + x)%13] += dp[i][j];
                    dp[i+1][(10*j + x)%13] %= mod; 
                }
            }
            else {
                ll x = s[i] - '0';
                dp[i+1][(10*j + x)%13] += dp[i][j];
                dp[i+1][(10*j + x)%13] %= mod;
            }
        }
    }

    out(dp[n][5]);
    re0;
}

Measured memory_bytes: 13696
#include<stdio.h>
 
int main(void){
	int values;
	int color[8];
	int exceed = 0;
	int N;
	values = scanf("%d",&N);
	int a[100];
	int i;
	for(i = 0;i < N;i++){
		values = scanf("%d",&a[i]);
	}
	for(i = 0;i < 8;i++){color[i] = 0;}
	
	for(i = 0;i < N;i++){
		if(a[i] < 400){
			color[0]++;
		}else if(a[i] < 800){
			color[1]++;
		}else if(a[i] < 1200){
			color[2]++;
		}else if(a[i] < 1600){
			color[3]++;
		}else if(a[i] < 2000){
			color[4]++;
		}else if(a[i] < 2400){
			color[5]++;
		}else if(a[i] < 2800){
			color[6]++;
		}else if(a[i] < 3200){
			color[7]++;
		}else{
			exceed++;
		}
	}
	int colors = 0;
	for(i = 0;i < 8;i++){
		if(color[i] > 0){colors++;exceed++;}
	}
	if(colors == 0 && exceed > 0){colors = 1;}
	printf("%d %d",colors,exceed);
	
	return 0;
}

Measured memory_bytes: 128
s = int(input())

a_list = []
a_list.append(s)
while True:
    if s%2 ==0:
        if s/2 in a_list:
            print(len(a_list)+1)
            break
        else: 
            a_list.append(s/2)
            s = s/2
    elif s%2 !=0:
        if (3*s)+1 in a_list:
            print(len(a_list)+1)
            break
        else:
            a_list.append((3*s)+1)
            s = (3*s)+1

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

using namespace std;

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  int K;
  cin >> K;
  bool ok = true;
  for (int i = 0; i < K && ok; i ++) {
    if (a[0] >= a[1])
      a[1] *= 2;
    else
      if (a[1] >= a[2])
        a[2] *= 2;
    if (a[0] < a[1] && a[1] < a[2])
      ok = false;
  }
  if (ok)
    cout << "No\n";
  else
    cout << "Yes\n";
  return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

class BIT{
  static const int MAX_N = 1 << 18;
  int n, bit[MAX_N+1];
public:
  BIT(int n_){
    n = n_;
    for(int i=0; i<n+1; i++) bit[i] = 0;
  }
  //a_1+...+a_iを計算する
  int sum(int i){
    int s = 0;
    while(i>0){
      s+=bit[i];
      i-=i&(-i);
    }
    return s;
  }
  //a_i += xをする(1<=i<=n)
  void add(int i, int x){
    while(i<=n){
      bit[i]+=x;
      i+=i&(-i);
    }
  }
};

struct ST {
  int type;
  int l, r;
};
bool operator<(const ST& a, const ST& b){
  if(a.l == b.l) return a.type < b.type;
  return a.l < b.l;
}

map<int,int> query[100005];

int main(){
  ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;

  vector<ST> pts;
  rep(i,N){
    int l, r;
    cin >> l >> r;
    pts.push_back((ST){0,l,r});
  }

  //コメントはrngさんの解説から
  // https://www.youtube.com/watch?v=Y9v0a4d0vzk
  for(int d=2; d<=M; d++){
    for(int p=1; d*(ll)p<=M; p++){ //この2重ループの計算量はO(M log M)
      //d*pを一番左端に持つような区間は何個？
      //<=> d*(p-1)を含まず、d*pを含むような区間は何個？
      //<=> Xを含まず、Yを含むような区間は何個？
      int X = d*(p-1);
      int Y = d*p;

      //すべての名産品の区間[l,r]を2次元平面の点p(l,r)にプロットしておくと、
      //「Xを含まず、Yを含むような区間にある名産品」は
      //「X<l<=YかつY<=rの範囲にある点の個数」で求められる。
      //
      // M |-----+-------+
      //   |     |*******|
      // r |-----+***p***|
      //   |     |*******|
      // Y |-----+---+---|
      //   |     |   |   |
      //   +--------------
      //         X   l   Y
      //

      //クエリは、左下を原点、右上を(l,r)とした間にある頂点数を求める。
      //(中間の長方形を求めるために、下、左、左下の部分の頂点数を求める)
      if(query[X].count(Y-1)==0){
        query[X][Y-1] = 1;
        pts.push_back((ST){1,X,Y-1});
      }
      if(query[X].count(100005)==0){
        query[X][100005] = 1;
        pts.push_back((ST){1,X,100005});
      }
      if(query[Y].count(Y-1)==0){
        query[Y][Y-1] = 1;
        pts.push_back((ST){1,Y,Y-1});
      }
      if(query[Y].count(100005)==0){
        query[Y][100005] = 1;
        pts.push_back((ST){1,Y,100005});
      }
    }
  }
  //FOR(it,query){
  //  pts.push_back((ST){1,(it->first).first,(it->first).second});
  //}
  
  //2次元平面上の「名産品」と「区間問い合わせクエリ」が既知なので、
  //l座標でソートしてlの小さい方から「点をマッピングするか」「クエリに答えるか」を行う
  sort(ALLOF(pts));

  BIT bit(1<<18);

  rep(i,pts.size()){
    if(pts[i].type == 0){
      bit.add(pts[i].r+1, 1);
    }else{
      query[pts[i].l][pts[i].r] = bit.sum(pts[i].r+1);
    }
  }

  //必要な情報がそろっているので、計算しなおして表示
  for(int d=1; d<=M; d++){
    if(d==1){
      cout << N << endl;
      continue;
    }
    int ret = 0;
    for(int p=1; d*(ll)p<=M; p++){
      int X = d*(p-1);
      int Y = d*p;

      ret += query[Y][100005] - query[Y][Y-1] - query[X][100005] + query[X][Y-1];
    }
    cout << ret << endl;
  }
 
  return 0;
}



Measured memory_bytes: 84452
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <math.h>

using namespace std;

int main(void)
{
	int n;
	cin >> n;
	map<string, int> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		m[s]++;
	}
	vector<pair<int, string> > l;
	for (auto &a : m) {
		l.push_back(make_pair(a.second, a.first));
	}
	sort(l.begin(), l.end());
	reverse(l.begin(), l.end());

	vector<string> answer;
	int number = l[0].first;
	for (int i = 0; i < l.size(); i++) {
		if (l[i].first == number)
			answer.push_back(l[i].second);
	}
	sort(answer.begin(), answer.end());

	for (auto& a : answer) {
		cout << a << endl;
	}


	return 0;
}


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

int n,a,b,p,A=0,B=0,C=0;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n>>a>>b;
	for(int i=0;i<n;i++){
		cin>>p;
		if(p<=a)
			A++;
		else if(p<=b)
			B++;
		else
			C++;
	}
	cout<<min(A,min(B,C));
	return 0;
}

Measured memory_bytes: 256
/* ex 7_1
   nknm */

#include <stdio.h>
#include <math.h>

typedef struct point{       //構造体を定義
    int x_elem;
    int y_elem;
}point;

point shift_point_3(point p1, point p2){        //p2を中心にp1を時計回りに90°回転させp3を求める
    point p3;
    p3.x_elem = p1.y_elem - p2.y_elem + p2.x_elem;
    p3.y_elem = p2.x_elem - p1.x_elem + p2.y_elem;
    
    return p3;
}
point shift_point_4(point p1, point p2){        //p1を中心にp2を反時計回りに90°回転させp4を求める
    point p4;
    p4.x_elem = p1.y_elem - p2.y_elem + p1.x_elem;
    p4.y_elem = p2.x_elem - p1.x_elem + p1.y_elem;
    return p4;
}

int main(void){

    int x1, y1, x2, y2;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

    point p1 = {x1, y1}, p2 = {x2, y2}, p3, p4;     //point型で定義

    p3 = shift_point_3(p1, p2);     //p3,p4を求める
    p4 = shift_point_4(p1, p2);

    printf("%d %d %d %d", p3.x_elem, p3.y_elem, p4.x_elem, p4.y_elem);

    return 0;
}

Measured memory_bytes: 1712
#include<bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
// greater<int>()
typedef long long ll;
ll GCD(ll x, ll y) { return y ? GCD(y, x % y) : x; }
ll LCM(ll x, ll y) { return x * y / GCD(x, y); }

using namespace std;
int main() {
	ll h = 0;

	cin >> h;

	ll x = 0;
	ll count = -1;
	while (h != 0)
	{
		h = h / 2;
		count++;
	}
	
	ll z = 1;
	ll ans = 1;
	for (int i = 0; i < count; i++)
	{
		z = 2 * z;
		ans += z;
	}

	cout << ans << endl;

}


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

int main()
{
    int i,j,l1,flag=0;
    char s[1000],t[1000],s2[1000];
    gets(s);
    gets(t);
    l1=strlen(s);
    for(j=0; j<=l1; j++)
    {

        for(i=1; s[i]!='\0'; i++)
        {
            s2[0]=s[l1-1];
            s2[i]=s[i-1];
        }
        for(i=0;i<l1;i++)
        {
            s[i]=s2[i];
        }
        if(strcmp(s,t)==0)
        {
            flag=1;
            break;
        }
    }
    if(flag==1) printf("Yes\n");
    else printf("No\n");
    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    //A - Cats and Dogs
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        int X = scanner.nextInt();
        if ( A <= X && X <= A + B) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }
}


Measured memory_bytes: 21716
import java.util.*;
 
class Main{
    public static void main(String[] args){
		char a = 'a';
		int[] arr = new int[26];
		Scanner scan = new Scanner(System.in);
		String str = "";
		while(scan.hasNext()) {
            String buf = scan.nextLine();
            str += buf;
        }

		char[] ch = str.toLowerCase().toCharArray();
		for(char alf : ch){
			for(int i=0; i<26; i++){
				if(alf==(a+i)){
					arr[i] += 1;
				}
			}
		}
		for(int i=0; i<26; i++){
			System.out.println((char)(a + i) + " : " + arr[i]);
		}
    }
}

Measured memory_bytes: 26356
from collections import defaultdict as dd
MOD = 10**9 + 7

def main():
    N, X = list(map(int, input().split()))
    S = list(map(int, input().split()))
    S = sorted(S, reverse=True)

    dp = dd(int)
    dp[X] = 1
    for i in range(N):
        new = dd(int)
        for x in dp:
            xx = x % S[i]
            new[x] += dp[x] * (N-i-1)
            new[x] %= MOD
            new[xx] += dp[x]
            new[xx] %= MOD
        dp = new

    total = 0
    for x in dp:
        total += dp[x] * x
        total %= MOD
    print(total)

main()


Measured memory_bytes: 5424
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define per1(i,n) for(int i=n;i>0;i--)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ans=0;
    rep(i,10)rep(j,10)rep(k,10){
        int z=0;
        rep(a,n){
            if(z==0&&s[a]-'0'==i) z=1;
            else if(z==1&&s[a]-'0'==j) z=2;
            else if(z==2&&s[a]-'0'==k) z=3;
        }
        if(z==3) ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 3680
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for i in range(M)]
for i in range(10**N): #rangeで書けば小さい順に実行するのを利用
    if len(str(i))==N and all(str(i)[s-1]==str(c) for s,c in sc):
                    #iの桁数指定では、入力のsと一つずれることに注意  
                    #このif文では最小値である可能性のある数字がリスト中にあるかどうか確認
        print(i)
        break
else:
    print(-1)

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

int main() {
	int A, B, K;
	cin >> A >> B >> K;
	int now = 0;
	for (int i = min(A, B); i >= 1; i--) {
		if (A % i == 0 && B % i == 0) {
			now++;
			if (now == K) {
				cout << i << endl;
				return 0;
			}
		}
	}
}


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

int main() {
int N;
cin >> N;
int card[4][13];

for(int i = 0; i < 13; i++){
        card[0][i] = 0;
        card[1][i] = 0;
        card[2][i] = 0;
        card[3][i] = 0;
    }
for (int i = 0; i < N; i++){
int n;
char S;
cin >> S >> n;
n--;
if(S == 'S'){
card[0][n]++;
}
else if(S == 'H'){
card[1][n]++;
}
else if(S == 'C'){
card[2][n]++;
}
else{
card[3][n]++;
}
}

for(int i = 0; i < 4; i++){
for(int j = 0; j < 13; j++){
if(card[i][j] == 0){
if(i == 0){
cout << "S " << j+1 << endl;
}
else if(i == 1){
cout << "H " << j+1 << endl;
}
else if(i == 2){
cout << "C " << j+1 << endl;
}
else{
cout << "D " << j+1 << endl;
}
}


}
}

}



Measured memory_bytes: 3064
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<vector>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <map>

using namespace std;


int main() {
    int K, X;
    cin >> K >> X;
    int pos_l = (X - K) + 1;
    int pos_r = (X + K);
    for (; pos_l < pos_r; pos_l++) {
        cout << (pos_l) << " ";
    }

    cout << endl;
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii; //2次元配列
typedef vector<ll> vll;
typedef vector<string> vs;

/*FUNCs=================================================*/



/*MAIN==================================================*/
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化

    int n; cin >> n;
    vi a(n+1); for(int i = 1; i < n+1; i++) cin >> a[i];
    vi answer(n+1,0);
    for(int i = 1; i < n+1; i++) {
        answer[a[i]] = i;
    }
    for(int i= 1; i< n+1; i++){
        cout << answer[i] << (i == n ? '\n' : ' ');
    }
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define int long long
#define P pair<int,int>
#define PP pair<P,int>
#define F first
#define S second
#define f(i,n) for(int i=0;i<(n);i++)
#define INF INT_MAX/3
#define eps LDBL_EPSILON
#define mod (int)(1000000007)
#define pie 3.141592653589793238462643383279
#define Bpri priority_queue
#define Spri priority_queue<P,vector<P>,greater<P>>
using namespace std;
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a*b/gcd(a,b);
}
signed main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	a--;
	cout<<b-b/c-b/d+b/lcm(c,d)-(a-a/c-a/d+a/lcm(c,d))<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
#include <iomanip>
using namespace std;

typedef struct {
	int h;
	int m;
	int estimate() {
		return h * 100 + m;
	}
}Time;
int main()
{
	int N, M;
	Time time;
	queue<int> tablen;
	queue<int> tablem;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> time.h >> time.m;
		tablen.push(time.estimate());
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> time.h >> time.m;
		tablem.push(time.estimate());
	}

	while(!tablen.empty() || !tablem.empty()){
		int h = 100000;
		int g = 100000;
		if (!tablen.empty()) {
			h = tablen.front();
		}
		if (!tablem.empty()) {
			g = tablem.front();
		}

		if(h==g){
			cout << g / 100 << ':' << setfill('0') << setw(2) << g % 100;
			tablem.pop();	tablen.pop();
		}
		else if (h > g) {
			cout << g / 100 << ':' << setfill('0') << setw(2) << g % 100;
			tablem.pop();
		}
		else {
			cout << h / 100 << ':' << setfill('0') << setw(2) << h % 100;
			tablen.pop();
		}

		if (!tablen.empty() || !tablem.empty())
			cout << ' ';
	}
	cout << endl;

	return 0;
}

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

int main() {
	cin.tie(0)->sync_with_stdio(false);

	int k, t; cin >> k >> t;
	vector<int> a(t);
	REP(i, t) cin >> a[i];

	sort(a.rbegin(), a.rend());
	int sum = accumulate(a.begin(), a.end(), 0);

	if (a[0] > k / 2) {
		cout << a[0] - 1 - (sum - a[0]) << '\n';
	} else
		cout << 0 << '\n';
	return 0;
}

Measured memory_bytes: 3576
# 入力
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))

INF = 10**20

# Y = A_1, .., A_N のときの X - Y の最小値を求める
# Y を決め打つと、 X - Y の最小値はO(NlogN)で求められる


def f(b):
    i = 0
    T = []
    while i < N:
        S = []
        while i < N and A[i] >= b:
            S.append(A[i])
            i += 1
        if len(S) >= K:
            T.extend(sorted(S)[:(len(S) - K + 1)])
        i += 1
    return (
        sorted(T)[Q - 1] if len(T) >= Q else
        INF
    )


ans = min(f(a) - a for a in sorted(A))

# 出力
print(ans)


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

using lint = long long;
const lint MOD = 1e9 + 7;
lint minv(lint n) {
    lint res = 1, p = MOD - 2;
    while (p > 0) {
        if (p % 2 == 1) {
            res = res * n % MOD;
        }
        n = n * n % MOD;
        p /= 2;
    }
    return res;
}
lint madd(lint a, lint b) {
    return (a + b) % MOD;
}
lint msub(lint a, lint b) {
    lint res = a - b;
    if (res < 0) {
        res += MOD;
    }
    return res;
}

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

    // 1 / n の累積和
    vector<lint> c(N + 1);
    for (int i = 1; i <= N; i++) {
        c[i] = madd(c[i - 1], minv(i));
    }

    lint ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += a[i] * madd(msub(c[i], c[0]), msub(c[N - i + 1], c[1])) % MOD;
    }
    for (int i = 1; i <= N; i++) {
        ans = ans * i % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<bits/stdc++.h>
#include<iomanip>
#include<math.h>
#include<vector>
#include<cctype>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
std::string line;

int main(){

    string s;
    cin >> s;
    int cnt = 0;
    rep(i,3) {
        if(s[i] == '1') ++cnt; 
    }
    cout << cnt << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>

const int N = 200 + 7;

int n, m;
char s[N][N];
int f[N][N][N], g[N][N][N];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", s[i] + 1);
		for (int j = m; j; --j) f[j][i][i] = s[i][j] == s[i][j + 1] ? f[j + 1][i][i] : j;
	}
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= n; ++j)
			for (int k = j + 1; k <= n; ++k) {
				f[i][j][k] = std::min(f[i][j][k - 1], f[i][k][k]);
				if (s[k][i] != s[k - 1][i]) f[i][j][k] = i - 1;
			}

	if (f[1][1][n] == m) return printf("0"), 0;
	for (int p = 1; ; ++p) {
		for (int i = 1; i <= m; ++i)
			for (int j = 1; j <= n; ++j) {
				g[i][j][j] = j - 1;
				for (int k = j + 1; k <= n; ++k)
					g[i][j][k] = f[i][j][k - 1] > f[i][j][k] ? k - 1 : g[i][j][k - 1];
			}
		for (int i = 1; i <= m; ++i)
			for (int j = 1; j <= n; ++j)
				for (int k = n, l = n; k >= j; --k) {
					if (f[i][j][k] == m) continue;
					f[i][j][k] = f[f[i][j][k] + 1][j][k];
					for (l = std::min(l, k - 1); l > j &&
						std::min(f[i][j][l], f[i][l + 1][k]) <
						std::min(f[i][j][g[i][j][l]], f[i][g[i][j][l] + 1][k]); --l);
					if (l >= j) f[i][j][k] = std::max(f[i][j][k], std::min(f[i][j][l], f[i][l + 1][k]));
				}
		if (f[1][1][n] == m) return printf("%d", p), 0;
	}
}


Measured memory_bytes: 65536
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string s, t, ans; int dp[3001][3001];
int main() {
  cin >> s >> t;
  for(int i = 0; i < s.size(); i++) {
    for(int j = 0; j < t.size(); j++) {
      if(s[i]==t[j]) dp[i+1][j+1] = dp[i][j]+1;
      else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
    }
  }
  for(int i = s.size(), j = t.size(); i > 0 && j > 0;) {
    if(dp[i][j]==dp[i-1][j]) i--;
    else if(dp[i][j]==dp[i][j-1]) j--;
    else {ans = s[i-1] + ans; i--; j--;}
  }
  cout << ans;
}

Measured memory_bytes: 35456
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] input = new int[n];
        for (int i = 0; i < n; i++) {
            input[i] = sc.nextInt();
        }

        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for(int i=1;i<n;i++){
            for(int j=1;j<=k;j++){
                //System.out.println("i=" + i + " j=" + j);
                if(i>=j) {
                    dp[i] = Math.min(dp[i], dp[i - j] + Math.abs(input[i] - input[i - j]));
                    //System.out.println("dp[" + i + "]=" + dp[i]);
                }
            }
        }

//        System.out.println("-----");
//        for(int i=0; i<n;i++){
//            System.out.println("dp[" + i + "]=" +dp[i]);
//        }

        System.out.println(dp[n-1]);



    }
}

Measured memory_bytes: 52148
while True:
    store = input().split()
    g = store[0]
    if g == '#':
        break
    y,m,d = map(int,store[1:])
    if y > 31 or (y == 31 and m > 4):
        print('? %d %d %d' % (y-30,m,d))
    else:
        print('HEISEI %d %d %d' % (y,m,d))



Measured memory_bytes: 5604
#include<cstdio>
#include<iostream>
using namespace std;
int md;
int dp[3010][3010][2];
void Add(int &x,int y){
	if(y>=md) y-=md;
	x=x+y;
	if(x>=md) x-=md;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	md=(int)1e9+7;
	for(int i=1;i<=n;i++)
		dp[0][i][0]=1;
	dp[0][0][1]=1;
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(j==0){
				Add(dp[i+1][j][1],dp[i][j][1]+dp[i][j][0]);
				Add(dp[i+1][j+1][1],dp[i][j][1]+dp[i][j][0]);
			}
			else if(j==1){
				Add(dp[i+1][j][1],dp[i][j][0]+dp[i][j][1]);
				if(j<n)
				{
					Add(dp[i+1][j][0],dp[i][j][0]);
					Add(dp[i+1][j][1],dp[i][j][1]);
					Add(dp[i+1][j+1][0],dp[i][j][0]);
					Add(dp[i+1][j+1][1],dp[i][j][1]);
				}
				Add(dp[i+1][j-1][1],dp[i][j][0]+dp[i][j][1]);
			}
			else if(j==n){
				for(int s=0;s<=1;s++){
					Add(dp[i+1][j][s],dp[i][j][s]);
					Add(dp[i+1][j-1][s],dp[i][j][s]);
				}
			}
			else{
				for(int s=0;s<=1;s++){
					Add(dp[i+1][j][s],dp[i][j][s]*2);
					Add(dp[i+1][j+1][s],dp[i][j][s]);
					Add(dp[i+1][j-1][s],dp[i][j][s]);
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++)
		Add(ans,dp[m][i][1]);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 70784
#include<bits/stdc++.h>
using namespace std;
#define INFTY 1<<20
typedef long long int ll;
const int MOD=1000000007;

struct  edge
{
    int u;
    int v;
    int cost;
};
edge es[100010];
int E,V;

struct UnionFind{
    vector<int> d;//d[i]:iの親の番号。根なら木のサイズ*(-1)
    UnionFind(int n=0):d(n,-1){}//全ての木のサイズが１と初期.n点
    
    int find(int x){//根を返す
    if(d[x] < 0) return x;//xが根の時はxを返す
    return d[x] = find(d[x]);
    }

    bool unite(int x,int y){//xとyの木をつなげたらtrue.大きい方に小さい方をつなげる.
    x = find(x);y = find(y);//根を求める
    if(x==y) return false;//同じ木に属していたらつなげる必要なし
    if(d[x]>d[y]) swap(x,y);//yの方がサイズが大きい時は交換する
    d[x] += d[y];//サイズの更新
    d[y] = x;//根の更新
    return true;
    }

    bool same(int x,int y){return find(x)==find(y);}//xとyが同じ木にあるか

    int size(int x){return -d[find(x)];}//xの木のサイズを返す
};
bool comp(const edge& e1,const edge& e2){
    return e1.cost < e2.cost;
}
int kruskal(){
    sort(es,es+E,comp);//edgecostの小さい順
    UnionFind uf(V);
    int res = 0;
    for (int i = 0; i < E; i++)
    {
        edge e = es[i];
        
        if(!uf.same(e.u,e.v)){
            res += e.cost;
            uf.unite(e.u,e.v);
        }
    }
    return res;
}
int main(){
    cin>>V>>E;
    for (int i = 0; i < E; i++)
    {
        int s,t,w;
        cin>>s>>t>>w;
        edge e = {s,t,w};
        es[i] = e;
    }
    int ans=kruskal();
  
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 4312
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char a[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','k','r','s','t','u','v','w','x','y','z'};
    string s;
    cin>>s;
    for(int i=0;i<26;i++)
    {
        int f=0;
        for(int j=0;j<s.size();j++)
        {
            if(s[j]==a[i]) f=1;
        }
        if(f==0) {cout<<a[i]<<endl;return 0;}
    }
    cout<<"None"<<endl;
    return 0;
}


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

#include <atcoder/all>

// #LIB#

using namespace std;
using namespace atcoder;
using ll = long long;
#define double long double
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x, c) for (auto&& x : (c))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))
#ifdef ONLINE_JUDGE
#define endl _endl
const char _endl = (cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout.precision(16), '\n');
#endif

int main() {
  ll n, q;
  cin >> n >> q;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  fenwick_tree<ll> t(n);
  rep(i, n) t.add(i, a[i]);
  rep(i, q) {
    ll qi, p, x;
    cin >> qi >> p >> x;
    if (qi == 0) {
      t.add(p, x);
    } else {
      cout << t.sum(p, x) << endl;
    }
  }
}


Measured memory_bytes: 12144
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();

        int n = sc.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        Arrays.sort(a);

        long ans = 0;
        for (int i = 1; i < n; i++) {
            ans += a[n - i/2 - 1];
        }

        System.out.println(ans);
    }

    static class MyScanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

Measured memory_bytes: 56364
#include <iostream>
#include <string>
using namespace std;
int main() {
    int K;
    string S;
    cin>>K;
    cin>>S;
    if(S.length()>K){
      string str=S.substr(0,K);
      
      cout<<str+"..."<<endl;
	}else{
      cout<<S<<endl;
    }
    return 0;
}

Measured memory_bytes: 3636