akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep_lr(i,l,r) for(int i=(l);i<(r);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
constexpr int INF = INT_MAX >> 1;
constexpr ll LINF = 5000000000000000LL;
constexpr int MOD = 1000000007;

int main() {

	int n, m;
	ll k;
	cin >> n >> m >> k;
	vi a(n), b(m);
	rep(i, n)cin >> a[i];
	rep(i, m)cin >> b[i];

	V<ll> suma(n + 1), sumb(m + 1);
	rep(i, n)suma[i + 1] = suma[i] + a[i];
	rep(i, m)sumb[i + 1] = sumb[i] + b[i];

	int ans = 0;
	rep(i, n + 1) {
		if (k - suma[i] < 0)continue;
		int aa = i;
		int bb = upper_bound(all(sumb), k - suma[i]) - sumb.begin();
		ans = max(ans, aa + bb);
	}
	cout << ans - 1 << endl;
}

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

int main() {
  int N, T;
  cin >> N >> T;
  vector<int> c(N), t(N);
  for (int i=0; i<N; i++) cin >> c.at(i) >> t.at(i);
  int minc=-1, mint=-1;
  for (int i=0; i<N; i++) {
    if (T < t.at(i)) continue;
    else {
      if (minc==-1||minc>c.at(i)) {
        minc = c.at(i); mint=t.at(i);
      }
    }
  }
  if (minc==-1) cout << "TLE" << endl;
  else cout << minc << endl;
}

Measured memory_bytes: 256
//This code was made by Chinese_zjc_.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#define int long long
#define INF 0x3fffffffffffffff
using namespace std;
int a,b;
signed main()
{
	std::ios::sync_with_stdio(false);
	cin>>b>>a;
	cout<<(b/a+(b%a>0));
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int l[20];
int main()
{
	int n;
	cin>>n;
	int sumx=0;
	for(int i=1;i<=n;i++)
	   cin>>l[i],sumx+=l[i];
	for(int i=1;i<=n;i++)
	   if(l[i]>=sumx-l[i]){
	      cout<<"No"<<endl;
	   	  return 0;
	   }
	cout<<"Yes"<<endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
S = [input() for i in range(N)]
march = {"M":0, "A":0, "R":0, "C":0, "H":0}

for i in S:
    if i[0] in march:
        march[i[0]] += 1

ans = 0
for key1, value1 in march.items():
    for key2, value2 in march.items():
        for key3, value3 in march.items():
            if key1 < key2 < key3:
                ans += value1 * value2 * value3

print(ans)

Measured memory_bytes: 9752
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pii pair <int,int>
#define pll pair <ll,ll>
#define testcase() int t; cin>>t; while(t--)
#define forn(i,n) for(int i=0;i<n;i++)
#define forn1(i,n) for(int i=1;i<=n;i++)
#define vll vector <ll>
#define all(v) v.begin(),v.end()

ll M = 1e9 + 7;
double pi = acos(-1.0);
ll powerm(ll x,ll y){ ll res=1; while(y){ if(y&1) res=(res*x)%M; y=y>>1; x=(x*x)%M;} return res%M; }
ll power(ll x,ll y){ ll res=1; while(y){ if(y&1) res=(res*x); y=y>>1; x=(x*x);} return res; }
ll max3(ll a,ll b,ll c){ return max( max(a,b),c ); }
ll gcd(ll a,ll b){if(b>a)return gcd(b,a); if(b==0)return a; return gcd(b,a%b);}
const int N = 1e5 + 5;
ll dp[N];

int main() {
	
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	
	int n,w; cin>>n>>w;
	forn(i,N) dp[i] = 1e18;
	dp[0] = 0;
	forn(i,n)
	{
	    ll a,b; cin>>a>>b;
	    for(int j=N-b-1;j>=0;j--) dp[j+b] = min(dp[j+b],dp[j]+a);
	}
	for(int i=N-1;i>=0;i--)
	{
	    if(dp[i]<=(ll)w){ cout<<i; return 0; }
	}
	cout<<0;
	return 0;
}


Measured memory_bytes: 1152
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

void zalgo(string& s,vector<int>& z){
    int c=0,n=s.length();
    z.resize(n,0);
    for(int i=1;i<n;++i){
        int l=i-c;
        if(i+z[l]<c+z[c]) z[i]=z[l];
        else{
            int j=max(0,c+z[c]-i);
            for(;i+j<n&&s[j]==s[i+j];++j);
            z[i]=j;c=i;
        }
    }
    z[0]=n;
}

class FStringsOfEternity {
public:
    void solve(istream& in, ostream& out) {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        string s,t,u;
        in>>s>>t;
        while(s.length()<t.length()) s+=s;
        int n=s.length(),l=t.length();
        s+=s;
        u=t+'|'+s;
        vector<int> z,p(n);
        zalgo(u,z);
        vector<bool> v(n);
        fr(i,n) if(z[l+1+i]==l) v[i]=1;
        fr(i,n) if(v[i]) p[(i+l)%n]=p[i]+1;
        fr(i,n) if(v[i]) p[(i+l)%n]=p[i]+1;
        int ans=0,a2=0;
        fr(i,n) ans=max(ans,p[i]);
        fr(i,n) if(v[i]) p[(i+l)%n]=p[i]+1;
        fr(i,n) a2=max(a2,p[i]);
        out<<(ans==a2?ans:-1)<<endl;
    }
};

int main() {
    FStringsOfEternity solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


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

int A[100001], n;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d", &A[i]);
    }

    int q, k, sum = 0;
    cin >> q;
    for(int i = 0; i < q; i++){
        scanf("%d", &k);
        if(*lower_bound(A, A+n, k) == k){
            sum++;
        }
    }

    cout << sum << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

void solve(int test_case) {
	ll sum = 0;
	string s;
	cin>>s;
	int n=s.length()-1;
	for(int i=0;i<1<<n;i++) {
		string temp="";
		for(int j=0;j<=n;j++) {
			temp+=s[j];
			if((i>>j)&1){
				cerr<<temp<<" "<<sum<<"\n";
				sum+=stoll(temp);
				temp="";
			}
		}
		if(temp!="") {
			sum+=stoll(temp);
		}
	}
	cout<<sum;
}

int main() {
	
	////// FILE BASED IO////
	//freopen("in", "r", stdin);
	//freopen("out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
}	


Measured memory_bytes: 3620
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;

/*--- Macro ---*/
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep1(i, n) for(int i=1; i<(int)n; i++)
#define mp make_pair
#define pb push_back

/*---  Type ---*/
typedef long long ll;

/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;

// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

// Util
int max(int a, int b, int c) {return max(a, max(b, c));}
int min(int a, int b, int c) {return min(a, min(b, c));}
ll max(ll x, ll y) {return x > y ? x : y;}
ll min(ll x, ll y) {return x < y ? x : y;}
ll max(ll a, ll b, ll c) {return max(a, max(b, c));}
ll min(ll a, ll b, ll c) {return min(a, min(b, c));}

// -------------------------------------------------------------------------------------

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

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

  int ans = 0;
  int k = 0, cnt = 0;
  rep(i, n) {
    if(k != a[i]) {
      ans += (cnt % 2 == 1 ? 1 : 0);
      k = a[i];
      cnt = 0;
    }
    cnt++;
  }
  ans += (cnt % 2 == 1 ? 1 : 0);

  cout << ans << endl;

  return 0;
}

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

int main( int argc, char *argv[] )
{
int a;
int b;
int h;

	ios::sync_with_stdio( false );
	cin.tie( 0 );

	cin >> a;
	cin >> b;
	cin >> h;
	cout << ( a + b ) * h / 2 << endl;

	return 0;
}




Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int start = sc.next().charAt(0) - 'A';
        int end = sc.next().charAt(0) - 'A';
        char[][] field = new char[h][];
        for (int i = 0; i < h; i++) {
            field[i] = sc.next().toCharArray();
        }
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (field[i][j] >= 'A' && field[i][j] <= 'Z') {
                    char a = field[i][j];
                    if (j + 2 < w && field[i][j + 2] == '-') {
                        int right = j + 2;
                        while (field[i][right] < 'A' || field[i][right] > 'Z') {
                            right++;
                        }
                        char b = field[i][right];
                        graph.get(a - 'A').add(b - 'A');
                        graph.get(b - 'A').add(a - 'A');
                    }
                    if (i + 2 < h && field[i + 2][j] == '|') {
                        int down = i + 2;
                        while (field[down][j] < 'A' || field[down][j] > 'Z') {
                            down++;
                        }
                        char b = field[down][j];
                        graph.get(a - 'A').add(b - 'A');
                        graph.get(b - 'A').add(a - 'A');
                    }
                }
            }
        }
        int[] costs = new int[26];
        Arrays.fill(costs, Integer.MAX_VALUE);
        PriorityQueue<Path> queue = new PriorityQueue<>();
        queue.add(new Path(start, 0));
        while (queue.size() > 0) {
            Path p = queue.poll();
            if (p.value >= costs[p.idx]) {
                continue;
            }
            costs[p.idx] = p.value;
            for (int x : graph.get(p.idx)) {
                queue.add(new Path(x, p.value + 1));
            }
        }
        System.out.println(costs[end]);
    }
    
    static class Path implements Comparable<Path> {
        int idx;
        int value;
        
        public Path (int idx, int value) {
            this.idx = idx;
            this.value = value;
        }
        
        public int compareTo(Path another) {
            return value - another.value;
        }
    }
}



Measured memory_bytes: 26480
n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new(0)
n.times do |i|
  h[a[i]] += 1
end
sum = 0
g = {}
f = {}
h.each do |k, v|
  sum += g[k] = v * (v - 1) / 2
  f[k] = (v - 1) * (v - 2) / 2
end
n.times do |i|
  puts sum - g[a[i]] + f[a[i]]
end

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

#define array_sort_asc(array,size) sort(array, array+size);
#define array_sort_desc(array,size) sort(array, array+size,greater<>());

int main() {
    int a,b;
    cin >> a >> b;

    if(a > 9 || b > 9) {
        cout << "-1" << endl;
        return 0;
    }

    cout << a*b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int M=1e9+7;
bool cmp(int a,int b){
	return a>b;}
int main(){
int n,m;
long long c=1;
cin>>n>>m;
set <int> at,bt;
int a[n],b[m];
for(int i=0;i<n;i++){
cin>>a[i];
at.insert(a[i]);}
for(int i=0;i<m;i++){
cin>>b[i];
bt.insert(b[i]);}
if(at.size()!=n||bt.size()!=m){
cout<<0;
return 0;}
int al=0,bl=0;
sort(a,a+n,cmp);
sort(b,b+m,cmp);
for(int i=n*m;i>0;i--){
	if((al<n&&bl<m)&&(i==a[al]&&i==b[bl])){
		al++;
		bl++;}
	else if(al<n&&i==a[al]){
		c*=bl;
		al++;}
	else if(bl<m&&i==b[bl]){
		c*=al;
		bl++;}
	else
	c*=(al*bl-(n*m-i));
	c%=M;}
cout<<c;}

Measured memory_bytes: 384
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);
const int INF = INT_MAX/10;

#include <complex>
typedef complex<double> P;
typedef vector<P> vP;
typedef vector<double> vd;

#define EQ(x,y) (abs((x)-(y))<EPS)

double rad(double deg) {
	return deg*PI/180.0;
}

double dot(P a, P b) {
	return (a.real()*b.real() + a.imag()*b.imag());
}

double cross(P a, P b) {
	return (a.real()*b.imag() - a.imag()*b.real());
}

double distance_ls_p(P a, P b, P c) {
	if(dot(b-a, c-a) < -EPS) return abs(c-a);
	if(dot(a-b, c-b) < -EPS) return abs(c-b);
	return abs(cross(b-a, c-a)) / abs(b-a);
}

int main() {
	double x1, y1, x2, y2, x3, y3, xp, yp;
	while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> xp >> yp) {
		P a(x1, y1), b(x2, y2), c(x3, y3), p(xp, yp);

		double S1 = abs(a-b) * distance_ls_p(a, b, c);
		double S2 = abs(a-b) * distance_ls_p(a, b, p);
		S2 += abs(b-c) * distance_ls_p(b, c, p);
		S2 += abs(c-a) * distance_ls_p(c, a, p);

		if(EQ(S1, S2)) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	}

	return 0;
}

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

typedef long long ll;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  string s;
  cin >> s;
  if(s[0] == s[1] && s[1] == s[2] || s[0] == s[2]) {
    cout << "Yes" << endl;
  }else cout << "No" << endl;
  return 0;
}


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

const int mod = 1e9+7;
int dp[44][(1<<18)][2];
int n,x,y,z;
int s;

bool ok(int mask)
{
    if((mask&(1<<z))==0) return false;
    if((mask&(1<<(y+z)))==0) return false;
    if((mask&(1<<s))==0) return false;
    return true;
}

int main()
{
    cin>>n>>x>>y>>z;
    s=x+y+z;
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int akt=1;akt<=10;akt++)
        {
            for(int pop=0;pop<(1<<(s+1));pop++)
            {
                for(int czy=0;czy<2;czy++)
                {
                    int nowa=(pop<<akt);
                    nowa|=(1<<akt);
                    nowa%=(1<<(s+1));
                    bool xd=ok(nowa);
                    if(xd || czy==1) dp[i][nowa][1]+=dp[i-1][pop][czy];
                    else
                    {
                        dp[i][nowa][0]+=dp[i-1][pop][czy];
                        if(dp[i][nowa][0]>=mod) dp[i][nowa][0]-=mod;
                    }
                    if(dp[i][nowa][1]>=mod) dp[i][nowa][1]-=mod;
                }
            }
        }
    }
    ll res=0;
    for(int i=0;i<(1<<(s+1));i++)
    {
        res+=dp[n][i][1];
        if(res>=mod) res-=mod;
    }
    cout<<res;
    return 0;
}


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

int main() {
	int k;cin>>k;
	int a,b;cin>>a>>b;
	int i=a;
	while(i<=b && i%k!=0){
	    i++;
	}
	if(i>b){cout<<"NG";}
	else{cout<<"OK";}
	return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
long long int k(int n,int w,long long int wt[],long long int val[]){
	long long int dp[n+1][w+1];
  for(int i=0;i<=n;i++){
  for(int j=0;j<=w;j++){
  	if(i==0||j==0){
    dp[i][j]=0;}
    else if(wt[i-1]<=j){
    	dp[i][j]=max(val[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j]);
    }
    else{
      dp[i][j]=dp[i-1][j];
    }
  }
  }
  return dp[n][w];
}
int main(){
int n,w;
cin>>n>>w;
  long long int wt[n],val[n];
  for(int i=0;i<n;i++){
  	cin>>wt[i]>>val[i];
  }
  cout<< k(n,w,wt,val)<<endl;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int N = s.size();
  string t;
  for (int i = 0; i < N; i++){
    if (s[i] != 'x'){
      t += s[i];
    }
  }
  string t2 = t;
  reverse(t2.begin(), t2.end());
  if (t != t2){
    cout << -1 << endl;
  } else {
    vector<int> cnt(1, 0);
    for (int i = 0; i < N; i++){
      if (s[i] == 'x'){
        cnt.back()++;
      } else {
        cnt.push_back(0);
      }
    }
    vector<int> cnt2 = cnt;
    reverse(cnt2.begin(), cnt2.end());
    int sz = cnt.size();
    int ans = 0;
    for (int i = 0; i < sz / 2; i++){
      ans += abs(cnt[i] - cnt2[i]);
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 4296
S = input()
LIST = list(S) #リストにすると、1文字毎に分割される。
lengs = len(LIST) #リス

count = int(0)

c = lengs // 2 


#中央は回文に必要ない要素なので処理しなくてもよい。

for i in range(c):
    #print(LIST[i])
    #print(LIST[lengs-i-1])
    #print("ばばばば")
    if LIST[i] == LIST[lengs-i-1]:
        count = count
    else:
        count = count  + 1
   
print(count)




















































Measured memory_bytes: 2940
#include<iostream>
#include<map>
#include<vector>
using namespace std;

int n;

typedef long long ll;

void solve()
{
	map<ll,int> M;
	vector<int> V;
	vector<int> res((n-1)/2,0);
	for(ll i=1;i<n;i++){
		int t=i*i%n;
		if(!M.count(t)){
			V.push_back(t);
			M[t]=0;
		}
	}

	for(int i=0;i<V.size();i++){
		for(int j=i+1;j<V.size();j++){
			int t=V[i]-V[j];
			if(t<0) t+=n;
			if(t>(n-1)/2) t=n-t;
			res[t-1]++;
		}
	}
	for(int i=0;i<res.size();i++)
		cout<<res[i]*2<<endl;

}

int main()
{
	while(cin>>n){
		if(n==0) break;
		solve();
	}
	return 0;
}

Measured memory_bytes: 1116
/*
 *
 *    I am o0o0oo00.
 *
 */
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll          long long
#define p7          1000000007
#define p9          998244353
#define pb          push_back
#define ff          first
#define ss          second
#define vll         vector<ll>
#define pll         pair<ll,ll>
#define vpll        vector<pll>
#define mll         map<ll,ll>
#define test        ll T;cin>>T;while(T--)
#define ad(a,n)     vll a;a.resize(n);for(ll i=0;i<n;i++)cin>>a[i];
#define as(a,n)     for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<endl;
#define all(x)      x.begin(),x.end()

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

ll powm(ll x, ll y, ll m = p7) {
    x = x % m; ll res = 1; while (y)
    {if (y & 1)res = res * x; res %= m; y = y >> 1; x = x * x; x %= m;} return res;
}
ll modi(ll a, ll m = p7) {return powm(a, m - 2, m);}
void yesno(bool f) {f ? cout << "YES" << endl : cout << "NO" << endl;}


void ss99()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}


int main()
{
//    ss99();
//   test
    {
        string s, t;
        cin >> s >> t;
        s = '_' + s;
        t = '_' + t;
        ll ns = s.size();
        ll nt = t.size();
        string ans = "";
        ll dp[ns + 1][nt + 1];
        for (ll i = 0; i <= ns; i++)
            for (ll j = 0; j <= nt; j++)
                dp[i][j] = 0;
        for (ll i = 1; i <= ns; i++)
        {
            for (ll j = 1; j <= nt; j++)
            {
                if (s[i] == t[j])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        ll i=ns-1,j=nt-1;
		while(1)
		{
			if(i==0 || j==0)
				break;
			else if(s[i]==t[j])
			{
				ans+=s[i];
				i--;
				j--;
			}
			else if(dp[i-1][j] >= dp[i][j])
			{
				i--;
			}
			else
			{
				j--;
			}
		}
		reverse(all(ans));
        cout << ans << endl;
    }
    return 0;
}

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

void prians(bool answer) {
  if(answer)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

int n, m, deleted = 0;
string s;
bool lst[200005] = {0};
vector<int> ab[200005][2];
int cnt[200005][2] = {0};
queue<int> qu;

bool solve();

int main() {
  int a, b, i;
  cin >> n >> m;
  cin >> s;
  for(i = 0; i < m; ++i) {
    cin >> a >> b;
    --a;
    --b;
    ab[a][s[b] - 'A'].push_back(b);
    ab[b][s[a] - 'A'].push_back(a);
  }
  for(i = 0; i < n; ++i)
    for(int j = 0; j < 2; ++j) cnt[i][j] = ab[i][j].size();
  for(i = 0; i < n; ++i)
    if(cnt[i][0] == 0 || cnt[i][1] == 0) {
      qu.push(i);
      ++deleted;
      lst[i] = 1;
    }
  prians(solve());
  return 0;
}

bool solve() {
  int now, i, k, to;
  while(qu.size() > 0) {
    now = qu.front();
    qu.pop();
    for(k = 0; k < 2; ++k)
      for(i = 0; i < ab[now][k].size(); ++i) {
        to = ab[now][k][i];
        if(!lst[to]) --cnt[to][s[now] - 'A'];
        if(!lst[to] && cnt[to][s[now] - 'A'] == 0) {
          lst[to] = 1;
          qu.push(to);
          ++deleted;
          if(deleted == n) return 0;
        }
      }
  }
  return deleted != n;
}


Measured memory_bytes: 20356
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

long long inputValueLongLong(){
    long long a;
    cin >> a;
    return a;
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int main(int argc, const char * argv[]) {
    
    // source code
    int r = inputValue();
    int res = r*r;
    cout << res <<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>


#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long
//#define lint long long

const int INF = 1e9;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで


using namespace std;
int n;
int a[300000];
int b;
int c;
vector<int> v;
signed main(){
  cin >> n;
  REP(i,n){
    cin >> a[i];
    b += a[i];
  }
  REP(i,n){
    c += a[i];
    if(i==n-1) continue;
    v.pb(abs(2*c-b));
  }
  sort(v.begin(),v.end());
  cout << v[0] << endl;
  return 0;
}


Measured memory_bytes: 3956
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))

s=0
pre=N
for a in A:
  s+=B[a-1]
  if pre == a-2:
    s+=C[pre]
  pre=a-1
print(s)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int s1,s2,s3,s,a1,a2,a3;
  cin >> s;
  s1 = s / 100;
  a1 = s % 100;
  s2 = a1 / 10;
  a2 = a1 % 10;
  s3 = a2;
  
  cout << s1 + s2 + s3 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    int a, b, q;
    cin >> a >> b >> q;

    vector<ll> s(a + 2), t(b + 2);
    s[0] = -1LL << 50;
    for (int i = 0; i < a; i++) {
        cin >> s[i + 1];
    }
    s[a + 1] = 1LL << 50;
    t[0] = -1LL << 50;
    for (int i = 0; i < b; i++) {
        cin >> t[i + 1];
    }
    t[b + 1] = 1LL << 50;

    for (int h = 0; h < q; h++) {
        ll x;
        cin >> x;

        ll z[4];
        auto it0 = lower_bound(s.begin(), s.end(), x);
        z[0] = *it0;
        z[1] = *(it0 - 1);
        auto it1 = lower_bound(t.begin(), t.end(), x);
        z[2] = *it1;
        z[3] = *(it1 - 1);

        for (int i = 0; i < 4; i++) {
            z[i] -= x;
        }

        ll r = 1LL << 60;
        for (int i = 0; i < 4; i++) {
            ll t = abs(z[i]);
            int j = (i / 2 ^ 1) * 2;
            t += min(abs(z[i] - z[j]), abs(z[i] - z[j + 1]));
            r = min(r, t);
        }
        cout << r << '\n';
    }
    cout << flush;

    return 0;
}

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

using ll = long long;

ll mod = 1e9 + 7;

ll modinv(long long a, long long m){
    long long b = m, u = 1, v = 0;
    while(b){
        long long t = a / b;
        a -= t * b; swap(a,b);
        u -= t * v; swap(u,v);
    }
    u %= m;
    if(u < 0) u += m;
    return u;
}


int main(){
    ll x, y;
    cin >> x >> y;
    ll ans = 0;
    bool flag = true;
    if(-x + 2*y < 0) flag = false;
    if(2*x - y < 0) flag = false;
    if((-x + 2*y) % 3 != 0) flag = false;
    if((2*x - y) % 3 != 0) flag = false;

    if(flag){
        ll a = (-x + 2*y)/3;
        ll b = (2*x - y)/3;
        ll p = 1, q = 1;
        rep(i,a){
            p *= (b + i + 1);
            q *= i + 1;
            p %= mod; q %= mod;
        }
        ans = p*modinv(q,mod) % mod;
    }

    cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>


using namespace std;

int main()
{
 int A,B,C;
 cin>>A>>B>>C;
 if(A>=(-100) && A<=100 &&B>=(-100) && B<=100 &&C>=(-100) && C<=100 ){

                if(A==B){cout<<C;}
 else if (A==C){cout<<B;}
 else if (B==C){cout<<A;}
        }



    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int N,D,M,A[MAXN],B[MAXN],s[MAXN],P[MAXN],cnt;
struct Bit
{
	int a[MAXN];
	void modify(int x,int v) {for (int i=x;i<=cnt;i+=i&(-i)) a[i]+=v;}
	long long ask(int x)
	{
		long long sum=0;
		for (int i=x;i;i-=i&(-i)) sum+=a[i];
		return sum;
	}
}T;
bool cmp(const int &a,const int &b) {return A[a]<A[b];}
int main()
{
	cin>>N>>D>>M;
	for (int i=1;i<=N;++i)
	{
		scanf("%d%d",&A[i],&B[i]),s[i]=A[i];
		if (B[i]%M==0) B[i]=B[i]/M;
		else B[i]=B[i]/M+1;
	}
	sort(s+1,s+1+N);
	cnt=unique(s+1,s+1+N)-s-1;
	for (int i=1;i<=N;++i) P[i]=i;
	sort(P+1,P+1+N,cmp);
	long long Ans=0;
	for (int i=1;i<=N;++i)
	{
		int x=A[P[i]];
		int v=B[P[i]];
		int p=lower_bound(s+1,s+1+cnt,x)-s;
		long long vv=T.ask(p);
		v=max(0LL,1LL*v-vv);
		Ans+=v;
		T.modify(p,v);
		p=upper_bound(s+1,s+1+cnt,min(1000000000LL,x+1LL*D*2))-s;
		T.modify(p,-v);
	}
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 4096
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		  try(Scanner sc = new Scanner(System.in)) {
			  while(sc.hasNext()) {
				  int m=sc.nextInt();
				  int n=sc.nextInt();
				  if(m==0 && n==0) break;
				  boolean[] tf=new boolean[n+1];
				  for(int i=1; i<=n; i++) {
					  tf[i]=false;
					  String s=sc.next();
					  
					  if(i%3==0 && i%5!=0 && s.equals("Fizz")) {
						  tf[i]=true;
					  }
					  else if(i%3!=0 && i%5==0 && s.equals("Buzz")) {
						  tf[i]=true;
					  }
					  else if(i%3==0 && i%5==0 && s.equals("FizzBuzz")) {
						  tf[i]=true;
					  }
					  else if(i%3!=0 && i%5!=0) {
						  String num=String.valueOf(i);
						  if(num.equals(s))
						  tf[i]=true;
					  }
					  //System.out.print(s.charAt(0));
				  }
				  
				  Queue <Integer> queue;
				  queue=new LinkedList<>();
				  for(int i=1; i<=m; i++) {
					  queue.add(i);
				  }
				  
				  for(int i=1; i<=n; i++) {
					  int p=queue.remove();
					  if(queue.isEmpty()) {
						  queue.add(p);
						  break;
					  }
					  if(tf[i]) {
						  queue.add(p);
					  }
				  }
				  int count=0;
				  boolean[] atf=new boolean[m+1];
				  for(int i=1; i<=m; i++) {
					  atf[i]=false;
				  }
				  while(! queue.isEmpty()) {
					  int ans=queue.remove();
					  atf[ans]=true;
				  }
				  for(int i=1; i<=m; i++){
					  if(atf[i]) {
						  if(count>0) System.out.print(" ");
						  System.out.print(i);
						  count++;
					  }
				  }
				  System.out.println();
				  
			  }
		}
	}
}


Measured memory_bytes: 73672
# 2019/04/12
# AtCoder Beginner Contest 097 - B

b = int(input())
max = 0

for i in range(1, 33):
    for j in range(2, 11):
        val = i**j
        if val > b:
            break
        
        if max < val:
            max = val

print(max)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define PI 				acos(-1)
#define mp				make_pair
#define pb				push_back
#define all(a)			(a).begin(), (a).end()
#define srt(a)			sort(all(a))
#define mem(a, h)		memset(a, (h), sizeof(a))
#define f 				first
#define s 				second
#define MOD				1000000007
#define MOD1			998244353
#define EPS				1e-9
#define fore(i, b, e)	for(ll i = b; i < e; i++)
#define forg(i, b, e, m)	for(ll i = b; i < e; i+=m)

using namespace std;

typedef long long 		ll;
typedef unsigned long long 		ull;
typedef pair<ll, ll>  ii;
typedef vector<ll>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
const ll tam = 10000010;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	//freopen("asd.txt", "r", stdin);
	//freopen("asd.txt", "w", stdout);
	int n;
	cin>>n;
	int res = 0, a;
	while(n--)
		cin>>a, res = __gcd(res, a);
	cout<<res<<'\n';
	return 0;
}

// read the question correctly (is y a vowel? what are the exact constralls?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs ll?) ARRAY OUT OF BOUNDSS2

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int q=sc.nextInt();
        int[] nums=new int[n];
        for(int i=0;i<q;i++){
            nums[sc.nextInt()-1]++;
        }
        for(int i=0;i<n;i++){
            if(k+nums[i]-q>0)System.out.println("Yes");
            else System.out.println("No");
        }
        
    }

    
}

Measured memory_bytes: 58672
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<math.h>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_map>
#pragma warning(disable: 4996)
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;


int main() {

	int N;
	cin >> N;
	while (N > 9) {
		N %= 10;
	}
	if (N == 3) {
		cout << "bon" << endl;
	}
	else if (N == 0 || N == 1 || N == 6 || N == 8) {
		cout << "pon" << endl;
	}
	else cout << "hon" << endl;


	return 0;
}

Measured memory_bytes: 3636
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    ans += a - 1;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)


YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, A: "List[int]", B: "List[int]"):
    task_index = {}
    for i in range(N):
        if B[i] in task_index:
            task_index[B[i]].append(A[i])
        else:
            task_index[B[i]] = [A[i]]

    sum_task_time = sum(A)
    dead_line_pool = []
    for i in B:
        heappush(dead_line_pool, -i)

    for _ in range(N):
        last_dead_line = -heappop(dead_line_pool)
        if sum_task_time > last_dead_line:
            print('No')
            return
        else:
            sum_task_time -= task_index[last_dead_line].pop()

    print('Yes')
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()


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

vector <pair<int,int>> T[100006];
int ans[100006];

void dfs(int v,int c,int p){
  int i;
  for(i = 0;i < T[v].size();i++){
    int u = T[v][i].first;
    int w = T[v][i].second;

    if(u == p) continue;
    if(w % 2 == 0) ans[u] = c;

    else{
      if(c == 1) ans[u] = 0;
      else ans[u] = 1;
    }
    dfs(u,ans[u],v);
  }
}

int main(){
  int n;
  int i,j;
  int u,v;
  ll x;

  scanf("%d", &n);

  for(i = 0;i < n - 1;i++){
    scanf("%d %d %lld", &u, &v, &x);
    T[u].push_back(make_pair(v,x));
    T[v].push_back(make_pair(u,x));
  }

  ans[1] = 0;

  dfs(1,0,-1);

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

  return 0;
}


Measured memory_bytes: 9216
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <math.h>
#include <cstring>

using namespace std;

#define REP(i,n)	for(int i=0;i<(n);++i)
#define REPS(i,s,t)	for(int i=(s);i<(t);++i)

#define INF 		2000000007
#define MOD			998244353

#define MAX 		100005

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int ll;


int dp[1100];

int main(void) {
	string R;cin>>R;
	bool flag = true;
 
	if(R[0]!='A') flag = false;
	if(R[1]<'a'||R[1]>'z')flag = false;
	int cnt = 0;
	int oomosi = 0;
	for(int i=1;i<R.size();++i){
		if(R[i]>='a' && R[i] <= 'z')continue;
		else if(R[i]=='C')cnt++;
		else oomosi++;
	}
	if(cnt != 1)flag = false;
	if(oomosi!=0)flag = false;
	if(R[R.size()-1]=='C')flag = false;
 
	cout << (flag ? "AC" : "WA") << endl;
 
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		char[] arr = sc.next().toCharArray();
		int count = 1;
		for (int i = 1; i < n; i++) {
		    if (arr[i] != arr[i - 1]) {
		        count++;
		    }
		}
		System.out.println(count);
   }
}


Measured memory_bytes: 26940
S = list(input())
S = [int(s) for s in S]
T = []
for s in range(len(S)):
    if s % 2 == 0:
        T.append(S[s]==0)
    else:
        T.append(S[s]==1)
U = []
for s in range(len(S)):
    if s % 2 == 0:
        U.append(S[s]==1)
    else:
        U.append(S[s]==0)
M = max(sum(T), sum(U))
print(len(S)-M)

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

int main() {
	int n;
	cin >> n;
	int mn,flg = 0;
	for(int i=1,x; i<=n; i++) {
		scanf("%d",&x);
		if(i == 1) mn = x-1;
		else {
			if(x < mn) {
				flg = 1;
				break;
			}
			if(x == mn) ;
			else mn = x-1;
		}
	}
	if(flg) puts("No");
	else puts("Yes");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;

typedef vector<int> VI;

int size[13] = {1, 2, 4, 2, 1, 4, 4, 4, 1, 2, 4, 2, 1};
int move[13][4] = {
  {2},
  {2, 5},
  {0, 1, 6, 3},
  {2, 7},
  {5},
  {1, 4, 6, 9},
  {2, 5, 7, 10},
  {3, 6, 8, 11},
  {7},
  {5, 10},
  {6, 9, 11, 12},
  {7, 10},
  {10}
};

VI v;
map<VI, int> mp;
map<VI, int> mp2;

void make(){
  VI goal;
  for(int i = 0 ; i < 13 ; i++){
    if(i == 0 || i == 12) goal.push_back(0);
    else goal.push_back(i);    
  }
  
  queue<VI> que;
  que.push(goal);
  mp2[goal] = 0;
  
  while(!que.empty()){
    VI q = que.front(); que.pop();    
    if(mp2[q] > 14) continue;
    for(int i = 0 ; i < 13 ; i++){
      if(q[i] != 0) continue;
      for(int j = 0 ; j < size[i] ; j++){
	VI t = q;
	swap(t[i], t[ move[i][j] ]);
	if(mp2.find(t) != mp2.end()) continue;	
	mp2[t] = mp2[q] + 1;	
	que.push(t);
      }
    }
  }
}
    


int bfs(){
  queue<VI> que;
  que.push(v);
  mp[v] = 0;  
  while(!que.empty()){
    VI q = que.front(); que.pop();    
    if(mp2.find(q) != mp2.end()){
      return mp2[q] + mp[q];
    }
    
    if(mp[q] > 7) continue;
    for(int i = 0 ; i < 13 ; i++){
      if(q[i] != 0) continue;      
      for(int j = 0 ; j < size[i] ; j++){
	VI t = q;
	swap(t[i], t[ move[i][j] ]);
	if(mp.find(t) != mp.end()) continue;
	mp[t] = mp[q] + 1;
	que.push(t);
      }
    }
  }
  return -1;
}

void init(){
  v.clear();
  mp.clear();  
}

int main(){
  make();
  int n;
  while(cin >> n){
    if(n == -1) break;
    
    init();
    
    v.push_back(n);
    for(int i = 0 ; i < 12 ; i++){ cin >> n; v.push_back(n); }
    
    int ans = bfs();
    if(ans == -1 || ans > 20) cout << "NA" << endl;
    else cout << ans << endl;
  }
  

  return 0;
}

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

typedef long long ll;

int main(){
    int h1 , m1, h2, m2, k = 0;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int wake = 0;
    if (m2 < m1){
        wake = m2+60 - m1 + ((h2-1)-h1)*60;
    } else {
        wake = m2-m1 + (h2-h1)*60;
    }
    if (k <= wake) {
        cout << wake - k << endl;
    }
    return 0;
}

Measured memory_bytes: 3148
//I am so vegetable
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define PB push_back
#define IN insert
#define ER erase
#define CT count
#define EP empty
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const double eps = 1e-6;
const double pi = acos(-1.0);
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
ll qpow(ll x, ll y) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans *= x; x *= x; }return ans; }
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; }return ans; }
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    ll X=x;
    x=y; y=X-a/b*y;
}
ll inv(ll x, int mod = MOD) { return qpow(x, mod - 2) % mod; }
ll m_m(ll a){ return (a%MOD+MOD)%MOD; }

int main() {
	//ofstream cout("E:\\acm dream\\out.txt",ios::out);
	FIO;
	long double a,b;cin>>a>>b;
    int h,m;cin>>h>>m;
    long double ans;
    h*=60;
    h+=m;
    long double hd = h/720.0*2*pi;
    long double md = m/60.0*2*pi;
    long double d = fabs(hd-md);
    if(d>pi)d = 2*pi-d;
    ans = sqrtl(a*a+b*b-2*a*b*cos(d));
    cout<<fixed<<setprecision(15)<<ans;
	return 0;
}

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

using namespace std;

const int max_n = 1000111, inf = 1000111222;

int n, q;
char s[max_n];

long long solve(int k) {
    long long d = 0, m = 0, dm = 0, dmc = 0;
    for (int i = 0; i < n; ++i) {
        if (i - k >= 0) {
            if (s[i - k] == 'D') {
                dm -= m;
                --d;
            } else if (s[i - k] == 'M') {
                --m;
            }
        }
        if (s[i] == 'D') {
            ++d;
        } else if (s[i] == 'M') {
            dm += d;
            ++m;
        } else if (s[i] == 'C') {
            dmc += dm;
        }
    }
    return dmc;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d%s%d", &n, s, &q);
    while (q--) {
        int k;
        scanf("%d", &k);
        printf("%lld\n", solve(k));
    }
    return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
int main()
{
	stack<double> s;
	double a, b;
	char c[80], bf;
	while (cin >> c)
	{
		if (c[0] == '+')
		{
			b = s.top(), s.pop();
			a = s.top(), s.pop();
			s.push(a+b);
		}
		else if (c[0] == '-' && c[1] == '\0')
		{
			b = s.top(), s.pop();
			a = s.top(), s.pop();
			s.push(a-b);
		}
		else if (c[0] == '*')
		{
			b = s.top(), s.pop();
			a = s.top(), s.pop();
			s.push(a*b);
		}
		else if (c[0] == '/')
		{
			b = s.top(), s.pop();
			a = s.top(), s.pop();
			s.push(a/b);
		}
		else
		{
			s.push(atof(c));
		}
		if ((bf = getchar()) == '\n')
			printf("%.6f\n", s.top());
		if (bf == EOF)
			return 0;
	}
}

Measured memory_bytes: 0
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

#[allow(unused_macros)]
macro_rules! debug {($($a:expr),*) => {println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}
#[allow(unused_macros)]
macro_rules! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> { fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering { self.0.partial_cmp(&other.0).unwrap() }}

#[allow(dead_code)]
const MAX:usize = 100006;
#[allow(dead_code)]
const INF_U32:u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32:i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64:u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64:i64 = 1 << 62;
#[allow(dead_code)]
const MOD:i64 = 1e9 as i64 + 7;


fn main() {
    input!{a:i64, b:i64};
    println!("{}", if a==1 && b==1 {"Draw"} else if a==1 {"Alice"} else if b==1 {"Bob"} else if a>b {"Alice"} else if a<b {"Bob"} else {"Draw"});
}


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

int main(){
  string s;cin >> s;int ans = 0;
  rep(i,s.length()-1){if(s[i] != s[i+1])ans += 1;}
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
def levenshtein(str1, str2):
    if len(str1) == 0 or len(str2) == 0: return max(len(str1), len(str2))
    # init
    dp = [[None for i in range(len(str2)+1)] for i in range(len(str1)+1)]
    for i in range(len(str1)+1): dp[i][0] = i
    for j in range(len(str2)+1): dp[0][j] = j

    for i in range(1, len(str1)+1):
        for j in range(1, len(str2)+1):
            val = dp[i-1][j-1] if str1[i-1] == str2[j-1] else dp[i-1][j-1]+1
            dp[i][j] = min(val, dp[i-1][j]+1, dp[i][j-1]+1)
    return dp[-1][-1]

s1 = input()
s2 = input()

print(levenshtein(s1, s2))


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

using std::min;

const int N=2e5+10;

int n,k,x[N];
char s[N];

void Init() {
	scanf("%d%d",&n,&k);
	scanf("%s",s);
	for (int i=0;i<n;++i) x[i]=s[i]-'A';
}

void Solve() {
	int p=0,op=0;
	for (int i=1;i<=min((n<<1|(k&1)),k);++i) {
		if ((x[p]^op)==0) x[p]^=1;
		else p=(p+1)%n,op^=1;
	}
	for (int i=0;i<n;++i) printf("%c",(x[(p+i)%n]^op)+'A'); putchar('\n');
}

int main() {
	Init();
	Solve();
	return 0;
}

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


int compare_int(const void *a, const void *b)
{
//    return *(int*)a - *(int*)b;
    return *(long long*)a - *(long long*)b;
}
//  qsort(A, b, sizeof(int), compare_int);

//long long  factorial(long long n) {
//    if (n > 0) {
//        return n * factorial(n - 1);
//    } else {
//        return 1;
//    }
//}
long long  factorial(long long n, long long depth) {
    if (n > 1) {
        depth++;
        return factorial(n / 2, depth);
    } else {
        return depth;
    }
}

int min(int a, int b) {
    if (a > b)
        return b;
    else
        return a;
}

int distance(int a, int b) {
  return abs(a-b)*abs(a-b);
}



//int ()
/*
int triangle(int a, int b, int c){
  if(a<b+c){
    if(b<c+a){
      if(c<a+b){
        printf("1\n");
        return 1;
      }
    }
  }
  printf("1\n");
  return 0;
}
*/

int main()
{
//  int  a ,b, c, d, e, X, Y ,r;
  long long  a, b, c, d, e, X, Y;
  //  double  c;
 long long  A[200003]={};
//  int  A[100003]={};
  int  B[100003]={};
  long long  C[100003][100001]={};

  int  flg=0;

//  char s[101][101]={};
  char s[100001]={};
  char t[100001]={};
//  int N, M;
//  int A[1000000001]={};
//  long long  C[101]={};
  int i,j,k;
  long long p=0,q=0;
//  int flag=0;
//  int tmp=0;
//  char tmp[101]={};
//  long long min=10000000000;
//  long long min=100000001;
  long long min =100000001;
  int len=0;
  int l=0;
//  int r=1000001;
  int cnt=0;
  int num=0;
  int num1=0;
  int num2=0;
  long long  ans=0;
  int ans_ac=0;
  int ans_wa=0;
  int max=0;
  long long sum=0;
  int addr=0;
  int ptn=0;
  int  tmp=0;
  double per=0; 
//  bool on_off[100]={};
  
//  char alp[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

  //  a=0;
  scanf("%lld", &a);
  for(i=0;i<a;i++){
    scanf("%lld", &A[i]);
//    printf("%lld ", A[i]);
    if(max<A[i]) max=A[i];
  }
  qsort(A, a, sizeof(long long), compare_int);
//  for(i=0;i<max+1;i++){
  for(i=0;i<max+1;i++){
    ans=0;
    for(j=0;j<a;j++){
      if(i<A[j]) ans=ans+((A[j]-i)*(A[j]-i));
      else ans=ans+((i-A[j])*(i-A[j]));
//    printf("%d\n", ans); 
    }
//    printf("%d\n", ans); 

    if(min>ans) min=ans;
  }

  
  printf("%lld\n", min); 
  
return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
constexpr int MX = 100005;
int n, l, r=MX*2;
ll a[MX], ac[MX], ans, m;
int main(){
	scanf("%d%lld", &n, &m);
	rep(i,n) scanf("%lld", a+i);
	sort(a,a+n, greater<ll>());
	rep(i,n) ac[i+1] = ac[i] + a[i];
	while(l+1 < r){
		int mid = (l+r) / 2, e = n;
		ll c = -m, hp = 0;
		rep(i,n){
			for(; e > 0 && a[i] + a[e-1] < mid; e--);
			c += e;
			hp += ac[e] + a[i] * e;
		}
		if(c >= 0) ans = hp - c * mid;
		(c >= 0 ? l : r) = mid;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 1792
#define lp(i,n) for(int i=0;i<n;i++)
#define pau system("pause")
#include<bits/stdc++.h>

using namespace std;
int main(){
    string s[3]={"Sunny","Cloudy","Rainy"};
    string a;
    cin>>a;
    lp(i,3){
        if(a==s[2]){
             cout<<s[0]<<endl;
             break;
        }
        else if(a==s[i]){
            cout<<s[i+1]<<endl;
            break;
        }
    }
}


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

int main() {
	std::string s;
	std::cin >> s;
	int ans = 0;
	for (int i = 0; i < s.size(); i++) {
		ans++;
		if (s[i] == s[i + 1]) {
			i += 2;
			if (i < s.size()) {
				ans++;
			}
		}
	}
	std::cout << ans;
}


Measured memory_bytes: 640