akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main() {
	int a,b,c,d,k; cin>>a>>b>>c>>d>>k;
	int h,m; h=c-a, m=d-b;
	cout<<max(0,h*60+m-k)<<endl;

	return 0;
}


Measured memory_bytes: 3620
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on
void main()
{
    auto input = stdin.byLine.map!split.joiner;

    long a;
    a = input.front.to!long;
    input.popFront;

    long b;
    b = input.front.to!long;
    input.popFront;

    long c;
    c = input.front.to!long;
    input.popFront;

    long d;
    d = input.front.to!long;
    input.popFront;

    solve(a, b, c, d);
}

void solve(long a, long b, long c, long d)
{
    max(a * c, a * d, b * c, b * d).writeln();
}


Measured memory_bytes: 3796
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int x = sc.nextInt();

        if(k*500>=x){
            System.out.println("Yes");

        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 21972
#include<iostream>
#include<cstdio>
using namespace std;
typedef struct result{
 long long int nam;
 long long int mon;
 long long int cont;
 long long int sum;
}P;
int main(){
  P a[4001];
  int n,nacount;
  while(1){
    cin >> n;
    nacount=0;
    if(n==0){break;}
    for(int i=0;i<n;i++){
      cin>>a[i].nam>>a[i].mon>>a[i].cont;
      a[i].sum=a[i].mon*a[i].cont;
    }
    for(int i=0;i<n;i++){
      for(int j=n-1;j>i;j--){
	if(a[i].nam==a[j].nam){
	  a[i].sum+=a[j].sum;
	  a[j].sum=0;
	}
      }
    }
    for(int i=0;i<n;i++){
      if(a[i].sum>=1000000){
	cout<<a[i].nam<<endl;
	nacount++;
      }
    }if(nacount==0){
      cout<<"NA"<<endl;
    }
  }
  return 0;
}

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

using namespace std;
int n;
map<string,vector<pair<int,int>>> least;
vector<string> l;
int main()
{
    //freopen("in.in", "r", stdin);

    cin>> n;
    for (int i = 1; i <= n ; i++){
    string s;
    int sc;
    cin>>s>>sc;
    if (least[s].size() == 0)l.push_back(s);
    least[s].push_back({sc,i});
    }

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

    for (int i = 0 ; i < l.size() ; i++){
    string j = l[i];
    sort(least[j].begin(),least[j].end());
    reverse(least[j].begin(),least[j].end());
    for (int h = 0 ; h < least[j].size() ; h++)cout<<least[j][h].second<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
// I am Varun Das from Jadavpur University
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define dbg(x) cerr << #x << " = " << x << endl
#define INF LLONG_MAX
#define loop(i,a,b) for(int i=a;i<b;i++)
using namespace std;
string s1,s2;
ll a[10000][10000],n,m;
vector<char>v;
int f(int i,int j){
	if(i==0 or j==0) return 0;
    if(s1[i-1]==s2[j-1]){
        v.push_back(i-1);
        f(i-1,j-1);
    }
    else{
        if(a[i-1][j] > a[i][j-1]){
        	f(i-1,j);
        }
        else{
        	f(i,j-1);
        }
    }
}
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//cout<<fixed<<setprecision(12);
string s1,s2;
cin>>s1>>s2;
n=s1.length(),m=s2.length();
memset(a,0,sizeof(a));
loop(i,0,n){
    loop(j,0,m){
        if(s1[i]==s2[j]){
            a[i+1][j+1]=a[i][j]+1;
        }
        else if(s1[i]!=s2[j]){
            a[i+1][j+1]=max(a[i+1][j],a[i][j+1]);
        }
    }
}
int i=n,j=m;
if(a[n][m] > 0){
while(j > 0 and i > 0){
	if(s1[i-1]==s2[j-1]){
		v.push_back(s1[i-1]);
		i-=1;
		j-=1;
	}
	else{
		if(a[i-1][j] > a[i][j-1]){
		i-=1;
		}
		else j-=1;
	}
}
}
else cout<<" ";
// f(n,m);
for(int i=v.size()-1;i>=0;i--) cout<<v[i];
// cout<<a[n][m]<<endl;
	return 0;
}

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

using namespace std;

int main() {
    int N, K;
    int F = 0;

    cin >> N >> K;
        
    int x;
    for (int i = 0; i < N; i++) {
        cin >> x;
        if (x >= K) {
            F++;
        }
    }

    cout << F;
}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
A = LIST()
B = LIST()
ans = sum(A)
for i in range(n):
    # while A[i] > 0:
    if A[i] <= B[i]:
        B[i] = B[i] - A[i]
        A[i] = 0

        # print(A)
        # print(B[i] - A[i])
        # print(B[i])
        # print(B)
        if A[i+1] <= B[i]:
            B[i] = B[i] - A[i+1]
            A[i+1] = 0

        else:
            A[i+1] = A[i+1] - B[i]
            B[i] = 0
            # print(A)
    else:
        A[i] = A[i] - B[i]
        B[i] = 0
        if A[i+1] <= B[i]:
            B[i] = B[i] - A[i+1]
            A[i+1] = 0

        else:
            A[i+1] = A[i+1] - B[i]
            B[i] = 0
    # print(A)
# print(A)
# print(A)
ans = ans-sum(A)
print(ans)

    





    # if A[i] > 0:
    #     B[i] -= 1
    #     A[i] -= 1
        
    # while(B[i] >= 0):
    #     B[i] = B[i] - A[i]

# for i in range(n):
#     if A[i] <= A[i+1]:
#         t = A[i+1]
#         c = A[i+1] - B[i]
#         c = max(0, c)
#         A[i+1] = c
#     else:
#         t = A[i]
#         c = A[i] - B[i]
#         c = max(0, c)
#         A[i] =c
# print(A)



Measured memory_bytes: 20552
from itertools import permutations
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

left = 0
r = 0
gen = [x for x in range(1, N+1)]
i = 1
for perm in permutations(gen):
    if perm == P:
        left = i

    if perm == Q:
        r = i
    i += 1

print(abs(left-r))


Measured memory_bytes: 3060
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <random>
#include <string>
#include <bitset>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <cstring>
#include <cstdlib>
#include <cctype>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define FORR(i, m, n) for(int i = m; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define INF 999999999

using namespace std;

typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

llong pow(int x, int n) {
    llong ans = x;
    if (n == 0) return 1;

    for(int i = 0; i < n - 1; i++) {
        ans *= x;
    }

    return ans;
}

void swap(int *X, int *Y){
    int t = *X; *X = *Y; *Y = t;
}

const static int MAX = 500;

int h, w;
char field[MAX][MAX];
bool flag = false, visited[MAX][MAX] = {false};

void dfs(int i, int j) {
    if (field[i][j] == 'g') {
        flag = true;
        return;
    }
    if (visited[i][j]) return;
    visited[i][j] = true;

    rep(k, 4) {
        if (0 <= i + dx[k] && i + dx[k] <= h - 1 && 0 <= j + dy[k] && j + dy[k] <= w - 1 && field[i + dx[k]][j + dy[k]] != '#') {
            dfs(i + dx[k], j + dy[k]);
        }
    }
}

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

    int cnt = 0;
    for (int i = a; i <= b; i++) {
        c = to_string(i);
        if (c[0] == c[4] && c[1] == c[3]) cnt++;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
// スタックサイズ: 100MB

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
using namespace std;

typedef int64_t ll;
const ll INF = 1000000000000000000;
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define vll vector<ll>
#define all(v) (v).begin(), (v).end()



int main() {

	ll N, Y;
	cin >> N >> Y;

	rep(i, N + 1) {
		rep(j, N + 1 - i) {
			ll k = N - i - j;

			if (10000 * i + 5000 * j + 1000 * k == Y) {
				cout << i << " " << j << " " << k << endl;
				return 0;
			}
		}
	}
	cout << -1 << " " << -1 << " " << -1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
using namespace std;
long long e=1e6+3,mod=1e9+9,pw[10005],f[10005][15];
int n,m,i,j;
string s,t;
int lcp(int x,int y)
{
	int i,s=0;
	for(i=14;i>=0;i--){
		if((y+(1<<i)-1)>n+n)continue;
		if(f[x][i]!=f[y][i])continue;
		x+=(1<<i);
		y+=(1<<i);
		s+=(1<<i);
	}
	return s;
}
string solve(string st)
{
	cerr<<st<<endl;
	st=" "+st;
	int i;
	fz1(i,n+n){
		f[i][0]=st[i];
	}
	fz1(j,14)fz1(i,n+n-(1<<j)+1){
		f[i][j]=(f[i][j-1]*pw[1<<(j-1)]+f[i+(1<<(j-1))][j-1])%mod;
	}
	int ans=1;
	for(i=2;i<=n+1;i++){
		int t=lcp(i,ans);
		if(st[ans+t]>st[i+t])ans=i;
//		cerr<<ans<<' '<<i<<' '<<t<<endl;
	}
	return st.substr(ans,n);
}
int main()
{
	pw[0]=1;
	fz1(i,10000){
		pw[i]=pw[i-1]*e%mod;
	}
	scanf("%d%d",&n,&m);
	m=min(18,m);
	rdst(s,5005);
	if(m--){
		t=s;reverse(t.begin(),t.end());
		s=solve(s+t);
	}
	int tt=0;while(tt<n&&s[0]==s[tt])tt++;
	int mem=tt;
	while(m--){
		tt*=2;
	}
	tt=min(tt,n);
	tt-=mem;
	fz1(i,tt)cout<<s[0];
	cout<<s.substr(0,n-tt)<<endl;
	return 0;
}

Measured memory_bytes: 1664
#include<stdio.h>


char check(int y,int x,int c_map[8][8]);

int main(){

	int i,j,map[8][8],flag=0;
	char ans;

	while(1){
		for(i=0;i<8;i++){
			if(scanf("%1d%1d%1d%1d%1d%1d%1d%1d",&map[i][0],&map[i][1],&map[i][2],&map[i][3],&map[i][4],&map[i][5],&map[i][6],&map[i][7])==EOF){
				flag=1;
				break;
			}

		}
		if(flag) break;

		for(i=0;i<8;i++){
			for(j=0;j<8;j++){
				if(map[i][j]==1){
					ans=check(i,j,map);
					flag=1;
					break;
				}

			}
			if(flag) break;
		}
		if(flag) flag=0;
		printf("%c\n",ans);
		scanf("%*c");
	}





	return 0;

}


char check(int y,int x,int c_map[8][8]){
	int map[12][12]={0},i,j;
	char rep;

	y+=2;
	x+=2;

	for(i=y;i<10;i++){
		for(j=2;j<10;j++){
			map[i][j]=c_map[i-2][j-2];
		}
	}

	if(map[y][x+2]==1) rep='C';
	else if(map[y+2][x]==1) rep='B';
	else if(map[y][x+1]==1){
		if(map[y+1][x]!=1) rep='E';
		else if(map[y+1][x-1]==1) rep='G';
		else rep='A';
	}
	else if(map[y+1][x]==1){
		if(map[y+1][x-1]==1) rep='D';
		else rep='F';
	}

	return rep;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll> > vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;
typedef pair<ll, ll> P;
const long long INF = numeric_limits<ll>::max();
const long long MOD = 1000000007;
const long double PI = 3.1415926;
template <class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
//char c;
 
#define Endl endl
 
/*--------------------template--------------------*/
int main() {
    ll N,M;
    cin>>N>>M;
    if (N==1 && M==1)cout<<1<<endl;
    else if(N==1)cout<<M-2<<endl;
    else if(M==1)cout<<N-2<<endl;
    else cout<<(N-2)*(M-2)<<endl;
    return 0;
}

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

using namespace std;

main() {
#ifdef HOME
    //freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, x, lst = 0, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        if (lst + 1 == x) {
            lst++;
        }
        else ans++;
    }
    if (ans == n) cout << -1;
    else cout << ans << '\n';
    return 0;
}



Measured memory_bytes: 384
s = input()
K = int(input())
sub = {s}
for d in range(1,6):
    for i in range(len(s)-d+1):
        sub |= {s[i:i+d]}
sub = list(sub)
n = len(sub)
for i in range(K):
    for j in range(n-i):
        a, b = sub[-i-1], sub[j]
        if a > b: sub[-i-1], sub[j] = b, a
print(sub[-K])

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

int n,m;
vector<vector<int>> graph;
vector<bool> visited;
vector<int> ans;

void dfs(int u){
    if(!visited[u]) ans.push_back(u);
    visited[u]=true;
    for(int v:graph[u]){
        if(visited[v]) continue;
        dfs(v);
        break;
    }
}

void solve(){
    cin >> n >> m;
    graph.resize(n);
    visited.resize(n);
    rep(i,0,m){
        int a,b;
        cin >> a >> b;
        --a;
        --b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(0);
    reverse(ans.begin(),ans.end());
    dfs(0);
    cout << ans.size() << endl;
    rep(i,0,ans.size()){
        cout << ans[i]+1;
        if(i==ans.size()-1) cout << endl;
        else cout << " ";
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


Measured memory_bytes: 9720
A,B,H,M=map(int,input().split())
import math

#thetaをつける

#長針の角度
a=(2*math.pi/12/60)*(H*60+M)

#短針の角度
b=(2*math.pi/60)*(M)

#角度の差
theta=a-b

#ans
print(math.sqrt(A**2+B**2-2*A*B*math.cos(theta)))


Measured memory_bytes: 9496
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

n=int(input())
a=lnii()

ans=deque([])
for i in range(n):
  if i%2==0:
    ans.appendleft(a[i])
  else:
    ans.append(a[i])

if n%2==0:
  ans=reversed(ans)

print(*ans)

Measured memory_bytes: 32296
N, K = map(int, input().split())

# if N == 2:
#     if K == 0:
#         print (1)
#         print (1, 2)
#         exit()
#     else:
#         print (-1)
#         exit()

# if N == 3:
#     if K == 0:
#         print (3)
#         print (1, 2)
#         print (2, 3)
#         print (1, 3)
#         exit()
#     elif K == 1:
#         print(2)
#         print (1, 2)
#         print (2, 3)
#         exit()
#     else:
#         print (-1)
#         exit()

# if N == 4:
#     if K == 0:
#         print (6)
#         for i in range(1, 5):
#             for j in range(i + 1, 5):
#                 print (i, j)
#         exit()
#     elif K == 1:
#         print (5)
#         for i in range(1, 5):
#             for j in range(i + 1, 5):
#                 if i == 3 and j == 4:
#                     pass
#                 else:
#                     print (i, j)
#         exit()
#     elif K == 2:
#         print (3)
#         for i in range(1, 4):
#             print (i, i + 1)
#         exit()
#     elif K == 3:
#         print (3)
#         for i in range(2, 5):
#             print (1, i)
#         exit()
#     else:
#         print (-1)
#         exit()

edge = [[0] * N for _ in range(N)] #1: 辺あり, 0: 辺なし
# print (edge) 

#必要な辺が多すぎるとき
if ((N - 1) * (N -2))//2 < K:
    print (-1)
    exit()

def output(lst): #リストをもらって答えをアウトプットする
    count = 0
    for i in lst:
        for j in i:
            if j == 1:
                count += 1
    print (count)
    for i in range(N):
        for j in range(N):
            if lst[i][j] == 1:
                if i <= j:
                    print (i + 1, j + 1)
                else:
                    print (j + 1, i + 1)
    return

for i in range(1, N): #1からすべての点に伸ばし、トータルで(n-1)C2の組を作る
    edge[0][i] = 1
    #あと何組減らさないといけないか
res = ((N - 1) * (N - 2)) //2 - K
#組を減らす必要があるときTrue
if res == 0:
    output(edge)
    exit()

tmp = 0
while True:
    tmp += 1
    for i in range(1, N):
        if res == 0:
            # flag = False
            output(edge)
            exit()
        if i + tmp < N:
            if i != i + tmp and edge[i][i + tmp] == 0 and edge[i + tmp][i] == 0:
                edge[i][i + tmp] = 1
                res -= 1
        else:
            if i != ((i + tmp) % N) + 1 and edge[i][((i + tmp) % N) + 1] == 0 and edge[((i + tmp) % N) + 1][i] == 0:
                edge[i][((i + tmp) % N) + 1] = 1
                res -= 1


Measured memory_bytes: 3700
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <iomanip>
#include <map>
#include <queue>
#include <list>

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
//#define RREP(i, n ,N) for(ll i = (N-1); i >= (n); i--)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl

#define vint vector<int>
#define vll vector<ll>

#define INF 1e9
#define PI 3.14159265359

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

using namespace std;
typedef long long  ll;

const long long MOD = 1e9+7;


int main(){
    string s, t;
    cin >> s >> t;

    int i = 0;
    int ans = 999999;
    while( i <= s.size() - t.size()){
        string sub = s.substr(i, t.size());
        int tmp = 0;
        REP(j, 0, t.size()){
            if(t[j] != sub[j]){
                tmp += 1;
            }
        }
        ans = min(ans, tmp);
        i += 1;
    }

    p(ans);

    return 0;
}


Measured memory_bytes: 3608
N, X = map(int, input().split())

def rep(N,X):
    if N == 1:
        if X == 1:
            return(0)
        elif X == 5:
            return(3)
        else:
            return(X-1)
    elif X == 1:
        return(0)
    else:
        n = 2**(N+2)-3
        p = 2**N-1 # N-1のPの個数
        if X <= n//2:
            return(rep(N-1, X-1))
        elif X == n//2+1:
            return(p + 1)
        else:
            if n-1 == X-1:
                return(rep(N-1, X-1-n//2-1) + p + 1)
            else:
                return(rep(N-1, X-1-n//2) + p + 1)
print(rep(N,X))


Measured memory_bytes: 3316
H,W,N = list(map(int,input().split()))

A = []

for i in range(N):
    a,b = list(map(int,input().split()))
    for j in range(3):
        for k in range(3):
            if a-j>0 and b-k>0 and a-j+2 < H+1 and b-k+2 < W+1:
                A.append(str(a-j)+" "+str(b-k))

from collections import Counter

counter = Counter(A)

from collections import defaultdict

dd=defaultdict(int)
count = 0
for k in counter.keys():
    dd[counter[k]]+=1
    count+=1
print((H-2)*(W-2)-count)
for i in range(1,10):
    print(dd[i])


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

def main():
    sa = input().split(' ')
    n = int(sa[0])
    a = int(sa[1])
    b = int(sa[2])

    c = 0
    for i in range(n + 1):
        k = i % 10 + int(i / 10) % 10 + int(i / 100) % 10 + int(i / 1000) % 10 + int(i / 10000) % 10
        if a <= k and k <= b:
            c += i

    print(c)


if __name__ == '__main__':
    main()



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

int main(int argc, char *argv[]){
  int n;
  while(cin >> n){
    if(n == 0)break;
    vector<int> taro(n);
    vector<int> hanako;
    for (int i = 0; i < n; i++) {
      cin >> taro[i];
    }
    sort(taro.begin(), taro.end());
    int p = 0;
    for (int i = 1; i <= 2*n; i++) {
      if(taro[p] == i){
        p++;
        continue; 
      }
      hanako.push_back(i);
    }
    int field = 0, turn = 0;
    while(!taro.empty() && !hanako.empty()){
      if(turn == 0){
        turn = 1;
        for (int i = 0; i < taro.size(); i++) {
          if(field < taro[i]){
            field = taro[i];
            taro.erase(taro.begin() + i);
            break;
          }
          if(i == taro.size() - 1){
            field = 0;
          }
        }
      }else{
        turn = 0;
        for (int i = 0; i < hanako.size(); i++) {
          if(field < hanako[i]){
            field = hanako[i];
            hanako.erase(hanako.begin() + i);
            break;
          }
          if(i == hanako.size() - 1){
            field = 0;
          }
        }
      }
    }
    std::cout << hanako.size() << std::endl;
    std::cout << taro.size() << std::endl;
  }
  return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define MOD 1000000007

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int arr[n];

    int x = 0;
    for(int i = 0; i<n; i++){
        cin>>arr[i];
        x ^= arr[i];
    }

    for (int i = 0; i < n; i++){
        arr[i] = x^arr[i];
        cout<<arr[i]<<" ";
    }

    return 0;
}

Measured memory_bytes: 4404
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

int N, M, Q, dp[555][555], l, r;

int main() {
  //freopen("input.in","r",stdin);
  //freopen("output.out","w",stdout);

  cin >> N >> M >> Q;
  for(int i = 0;i < M;i++) {
    cin >> l >> r;
    dp[l][r]++;
  }

  for(int i = N;i >= 1;i--) {
    for(int j = 1;j <= N;j++) {
      dp[i][j] += (dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]);
    }
  }

  while (Q--) {
    cin >> l >> r;
    cout << dp[l][r] << endl;
  }

  return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
#include<map>
using namespace std;
int main()
{
    int n;
    cin>>n;
    long long int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    // map<long long int,int> mp;
    // int b[n];
    // int dis=0;
    // for(int j=0;j<n;j++)
    // {
    //     if(mp[a[j]] == 0)
    //     {
    //         mp[a[j]]++;
    //         b[dis++] = a[j];
    //     }
    
    // }
    long long int count  = 0;
    for(int i=0; i< n ;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                if(a[i] != a[j] && a[j]!= a[k] && a[i] != a[k])
                {
                    if((a[i] + a[j] > a[k]) && (a[j]+a[k] > a[i]) && (a[i]+a[k] > a[j]) )
                    count++;
                }
            }
        }
    }
    cout<<count<<endl;
    return 0;
}

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

long long n, a[100010], s, k;

int main() {
    scanf("%lld", &n); k = n*(n+1)/2;
    for(int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        s += a[i];
    }
    if(s % k != 0) return !printf("NO");
    k = s/k;
    for(int i = 0; i < n; i++) {
        int d = k - (a[(i+1)%n] - a[i]);
        if(d < 0 || d % n != 0) return !printf("NO");
    }
    printf("YES");
}


Measured memory_bytes: 1024
N = int(input())
K = int(input())

res = 0
if K == 1:
    for i in range(1,10):
        for j in range(len(str(N))):
            if i*10**j <= N:
                res += 1
if K == 2:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for j1 in range(len(str(N))-1):
                for j2 in range(len(str(N))-1-j1):
                    if i1*10**(j1+j2+1)+i2*10**j2 <= N:
                        res += 1

if K == 3:
    for j1 in range(len(str(N))-2-1):
        for j2 in range(len(str(N))-2-1-j1):
            for j3 in range(len(str(N))-2-1-j1-j2):
                res += 1
    res = res * (9**3)
    
    for j1 in range(len(str(N))-2):
        for j2 in range(len(str(N))-2-j1):
            j3 = len(str(N))-2-j1-j2-1
            for i1 in range(1,10):
                for i2 in range(1,10):
                    for i3 in range(9,0,-1):
                        if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N:
                            res += i3
                            break

print(res)


Measured memory_bytes: 3188
// --https://kenkoooo.com/atcoder/#/table/soma62jp
#include <iostream>

#define	MOD	1000000007

using namespace std;

int main(int argc, char* argv[]) {

	long long N, ans;

	cin >> N;

	ans = 1;
	for (long long i = 1; i <= N; i++) {
		ans = (ans * i) % MOD;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
const int inf = 1e9;

int main(){
	while(1){
		int n;
		cin >> n;
		if(n==0) break;
		vector<vector<int> > cost(n,vector<int>(n+1));
		for(int i=0; i<n; i++){
			for(int j=0; j<n+1; j++){
				cin >> cost[i][j];
			}
		}
		
		//make adjlist 
		vector<vector<pair<int,int> > > adj(1<<n);
		for(int i=0; i<(1<<n); i++){
			for(int b=0; b<n; b++){
				if((i&(1<<b)) == 0){
					int c=cost[b][0];
					for(int j=0; j<n; j++){
						if((i&(1<<j)) != 0){
							c = min(c, cost[b][j+1]);
						}
					}
					adj[i].push_back(make_pair(i|(1<<b), c));
				}
			}
		}
		
		//dijkstra
		priority_queue<pair<int,int> > pq;
		pq.push(make_pair(0,0));
		vector<int> mc(1<<n, inf);
		while(!pq.empty()){
			int cpos = pq.top().first;
			int ccost = -pq.top().second;
			pq.pop();
			if(cpos == 1<<n) break;
			if(ccost > mc[cpos]) continue;
			
			for(int i=0; i<(int)adj[cpos].size(); i++){
				int dest = adj[cpos][i].first;
				int cost = adj[cpos][i].second;
				if(ccost +cost < mc[dest]){
					mc[dest] = ccost+cost;
					pq.push(make_pair(dest, -mc[dest]));
				}
			}
		}
		
		cout << mc[(1<<n)-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 11260
import java.util.Scanner;
public class Main{ 
	public static void main(String[] args) {
	Scanner input = new Scanner (System.in);
	int s;
   int n = input.nextInt();
   int k = input.nextInt();
   int x = input.nextInt();
   int y = input.nextInt();
 s=Math.min(n,k) * x +Math.max(n-k,0)*y;
 System.out.println(s);
   
}}

Measured memory_bytes: 26900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

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;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

bool is_prime[1000010];

int main() {
    int n,x,y;
    cin >> n >> x >> y;
    x--,y--;
    vector<vector<int>> dist(n,vector<int>(n,-1));
    for (int s = 0; s < n; ++s) {
        queue<int> q;
        q.push(s);
        dist[s][s] = 0;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            vector<int> next;
            if(v > 0) next.push_back(v-1);
            if(v < n-1) next.push_back(v+1);
            if(v == x) next.push_back(y);
            if(v == y) next.push_back(x);

            for(auto nv:next){
                if(dist[s][nv] == -1){
                    dist[s][nv] = dist[s][v]+1;
                    q.push(nv);
                }
            }
        }
    }
    vector<int> ans(n,0);
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            ans[dist[i][j]]++;
        }
    }
    for (int i = 1; i < n; ++i) {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 19000
n = int(input())
a_list = [int(x) for x in input().split()]

temp = 0
c = 1
for i in range(n):
    temp += c * a_list[i]
    c *= -1

ans_list = [temp]
for i in range(n - 1):
    ans_list.append(2 * (a_list[i] - ans_list[i] // 2))
print(" ".join([str(ans) for ans in ans_list]))


Measured memory_bytes: 19100
#include <bits/stdc++.h>
using namespace std;
int main(){
  int h,w,cnt=0;
  cin >> h >> w;
  char a[h][w];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> a[i][j];
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j]=='#') cnt++;
    }
  }
  if(cnt!=h+w-1) cout << "Impossible" << endl;
  else cout << "Possible" << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using vll = vector<ll>;

void solve();

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

  solve();

  return 0;
}

#define ini(...)   \
  int __VA_ARGS__; \
  in(__VA_ARGS__)

#define inl(...)  \
  ll __VA_ARGS__; \
  in(__VA_ARGS__)

#define ins(...)      \
  string __VA_ARGS__; \
  in(__VA_ARGS__);

#define inc(...)      \
  char __VA_ARGS__; \
  in(__VA_ARGS__);

void in() {}
template <typename T, class... U>
void in(T& t, U&... u) {
  cin >> t;
  in(u...);
}

void out() {
  cout << endl;
}
template <typename T, class... U>
void out(const T& t, const U&... u) {
  cout << t;
  if (sizeof...(u))
    cout << " ";
  out(u...);
}

#define rep(i, n) for (long long i = 0; i < n; i++)

void solve();
#ifndef ONLINE_JUDGE
#include "./lib.hpp"
#endif

void solve() {
  ini(N);
  vll A(N);
  rep(i, N) cin >> A[i];

  ll money = 1000;
  rep(i, N - 1) {
    if (A[i] < A[i + 1])
      money += (money / A[i]) * (A[i + 1] - A[i]);
  }
  out(money);
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;constexpr const char nl='\n',sp=' ';

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // freopen("err.txt", "w", stderr);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a, b, c;
    cin >> a >> b >> c;
    cout << (c - a - b >= 0 && 4 * a * b < (c - a - b) * (c - a - b) ? "Yes" : "No") << nl;
    return 0;
}


Measured memory_bytes: 256
n=int(input())
s=[]
t=[]
for i in range(n):
    sn,tn=map(str,input().split())
    s.append(sn)
    t.append(int(tn))
x=input()

ans=sum(t)
for i in range(n):
    ans-=t[i]
    if s[i]==x:
        break

print(ans)


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

using namespace std;

long long mod = 1e9+7;

long long pot(long long a, long long b){
	if(b<=0) return 1;
	if(b%2==0){
		long long cur = pot(a, b/2);
		return (cur*cur)%mod;
	}else return (pot(a, b-1)*a)%mod;
}

int main(){
	
	long long wyn = 2;
	long long n; cin>>n;
	if(n<2) {cout<<0; return 0;}
	/*for(int i = 2; i <= n; i++){
		int tmp = 1;
		tmp*=pot(9, i);
		tmp*=pot(10, n-i-2)
	}*/
	wyn = (pot(10, n) - 2*pot(9, n) + pot(8, n)+10*mod)%mod;
	cout<<wyn;
	return 0;
}


Measured memory_bytes: 3540
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <map>
using namespace std;
const int MAXN = 1000005;
char S[MAXN], T[MAXN];
int n, q[MAXN], head = 1, tail;
signed main () {
	scanf("%d%s%s", &n, S+1, T+1);
	if(strcmp(S+1, T+1) == 0) { puts("0"); return 0; }
	int ans = 0;
	for(int i = n, j = n; i >= 1; --i) {
		if(T[i] == T[i-1]) continue;
		j = min(j, i);
		for(; j && S[j] != T[i]; --j);
		if(!j) { puts("-1"); return 0; }
		while(head <= tail && q[head] - (tail-head+1) + 1 > i) ++head;
		q[++tail] = j;
		if(i != j) ans = max(ans, tail-head+1);
	}
	printf("%d\n", ans+1);
}

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

int main(){
    int a,b,c,d,e;
    cin >> a >> b >> c >> d >> e;
    if(a==0){
        cout << 1 << endl;
    }
    else if(b==0){
        cout << 2 << endl;
    }
    else if(c==0){
        cout << 3 << endl;
    }
    else if(d==0){
        cout << 4 << endl;
    }
    else if(e==0){
        cout << 5 << endl;
    }
    

    return 0;
}

Measured memory_bytes: 3620
#include <iostream>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int n, a[100000]; char op[100000];
long long dp[100010][3];

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	cin >> n;
	op[0] = '+';
	rep(i, n){
		cin >> a[i];
		if(i != n - 1) cin >> op[i + 1];
	}
	rep(i, n + 1) rep(j, 3) dp[i][j] = -1e18;
	dp[0][0] = 0;
	rep(i, n) rep(j, 3) if(dp[i][j] > -1e18){
		if(j < 2 && op[i] == '-'){
			int nj = j + 1;
			dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + (j & 1 ? a[i] : -a[i]));
		}
		for(int nj = j; nj >= 0; nj--){
			dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + (j & 1 ^ op[i] == '+' ? a[i] : -a[i]));
		}
	}
	cout << dp[n][0] << endl;
	return 0;
}

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

#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define all(x) (x).begin(),(x).end()
#define fst first
#define sec	second
#define pb push_back

typedef long long ll;
typedef vector<int> vi;
typedef pair<long,long> P;

const int mod = 1e9 + 7;


int main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	int n;
	cin >> n;

	pair<pair<string, int>, int> v[110];
	rep(i, n){
		cin >> v[i].first.first >> v[i].first.second;
		v[i].first.second = v[i].first.second * -1;
		v[i].second = i+1;
	}
	
	sort(v, v+n);

	rep(i, n){
		cout << v[i].second << endl;
	}


    return 0;
}



Measured memory_bytes: 256
N=int(input())
count=1
a=[]
for i in range(N):
  x1,l1=map(int,input().split())
  a.append([x1+l1,x1-l1])
a.sort()
migi=a[0][0]
for i in range(N):
  if(a[i][1]>=migi):
    count+=1
    migi=a[i][0]
print(count)

Measured memory_bytes: 20104
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

#define X first
#define Y second

//#include <boost/unordered_map.hpp>
//using namespace boost;

/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/

namespace io{
	const int L = (1 << 20) + 1;

	char buf[L], *S , *T, c;

	char getchar() {
		if(__builtin_expect(S == T, 0)) {
			T = (S = buf) + fread(buf, 1, L, stdin);
			return (S == T ? EOF : *S++);
		}
		return *S++;
	}

	int inp() {
		int x = 0, f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}

	unsigned inpu()
	{
		unsigned x = 0; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar());
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x;
	}

	ll inp_ll() {
		ll x = 0; int f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}

	char B[45], *outs=B+40, *outr=B+40;
	template<class T>
	inline void print(register T a,register char x=0){
		if(x) *--outs = x, x = 0;

		if(!a)*--outs = '0';
		else
			while(a)
				*--outs = (a % 10) + 48, a /= 10;

		if(x)
			*--outs = x;

		fwrite(outs, outr - outs , 1, stdout);
		outs = outr;
	}
};

using io :: print;
using io :: inp;
using io :: inpu;
using io :: inp_ll;

using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
//using i128 = __int128_t;
//using u128 = __uint128_t;
using i128 = i64;
using u128 = u64;

ll power(ll a, ll b, ll p)
{
	if (!b) return 1;
	ll t = power(a, b/2, p);
	t = t*t%p;
	if (b&1) t = t*a%p;
	return t;
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	ll px, py;
	ll d = exgcd(b, a%b, px, py);
	x = py;
	y = px-a/b*py;
	return d;
}

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

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

const int MOD = 1000003;
const int INF = 1000000000;
const int MAXN = 200010;
const int MAXK = 18;

int n, m;
char s[MAXN], a[MAXN];

int main()
{
	
	cin >> s+1;
	n = strlen(s+1);
	m = 0;
	for (int i = 1; i <= n; ++ i)
	{
		if (s[i] == 'B' && s[i+1] == 'C')
		{
			a[++ m] = 'D';
			++ i;
		}
		else
			a[++ m] = s[i];
	}
	
	int cnt = 0;
	ll ans = 0;
	for (int i = 1; i <= m; ++ i)
	{
		if (a[i] == 'A')
			++ cnt;
		else if (a[i] == 'D')
			ans += cnt;
		else
			cnt = 0;
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define dp second
#define x first
using namespace std;
typedef pair<int,int> ii;
const int inf = 1023456;

int A[200005];
int dp[200005]; ///dp[i][0] 
int h1[200005]; ///smallest j such that dp[i][j] = dp[i][0] - 1  
int h2[200005]; ///smallest j such that dp[i][j] = dp[i][0] - 2  

inline int cost(int i, int x1, int x2){
	int y1 = A[i-1] - x1, y2 = A[i] - x2;
	return (x1 > x2) + (y1 < y2);
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	for(int i = 1;i <= n;i++) cin >> A[i];
	
	fill(dp,dp+200005,inf); dp[0] = 0;
	h1[0] = inf; h2[0] = inf;
			
	for(int i = 1;i <= n+1;i++){
		vector<ii> pre = { ii(0,dp[i-1]) };
		if(h1[i-1] != inf) pre.push_back(ii(h1[i-1], dp[i-1] - 1));
		if(h2[i-1] != inf) pre.push_back(ii(h2[i-1], dp[i-1] - 2));
		
		for(ii p : pre) dp[i] = min(dp[i], p.dp + cost(i, p.x, 0));
		
		int bestDP = inf;
		for(ii p : pre) bestDP = min(bestDP, p.dp + cost(i, p.x, A[i]));
		

		if(bestDP <= dp[i] - 1){
			
			///binary search for h1[i]
			int low = 0, high = A[i];
			while(low != high - 1){
				int s = (low + high) / 2;
				int val = inf;
				for(ii p : pre) val = min(val, p.dp + cost(i, p.x, s));
				if(val > dp[i] - 1) low = s;
				else high = s;
			}
			
			h1[i] = high;
		}
		else h1[i] = inf; ///not possible to achieve dp[i][0] - 1
		
		
		if(bestDP <= dp[i] - 2){
			
			///binary search for h2[i]
			int low = 0, high = A[i];
			while(low != high - 1){
				int s = (low + high) / 2;
				int val = inf;
				for(ii p : pre) val = min(val, p.dp + cost(i, p.x, s));
				if(val > dp[i] - 2) low = s;
				else high = s;
			}
			
			h2[i] = high;
		}
		else h2[i] = inf; ///not possible to achieve dp[i][0] - 2
	}
	
	cout << dp[n+1];
}


Measured memory_bytes: 3328
MAX = 600000
MOD = 10 ** 9 + 7
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD

def combinations(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD


N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
com = [0]
for i in range(N):
    com.append(A[i] + com[-1])
#print(com)
ans = 0
for i in range(K-2,N-1):
    ans += combinations(i,K-2) * (-(com[N-i-1]) + (com[N]-com[i+1]))
    #print(N-i-1,N,i+1)
    ans %= MOD
    #print(combinations(i,K-2) * (-(com[N-i-1]) + (com[N]-com[i+1])))
print(ans)



Measured memory_bytes: 100532
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
const ll MOD=1e9+7;
const int INF=1<<30;

int main(){
  int m1,d1;
  cin >> m1 >> d1;
  int m2,d2;
  cin >> m2 >> d2;
  if(m1==m2)
    cout << 0 << endl;
  else
    cout << 1 << endl;
  
  
}

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

int main() {
  string s;
  int count = 0;
  cin >> s;
  if (s[0] == '1') count++;
  if (s[1] == '1') count++;
  if (s[2] == '1') count++;
  cout << count << endl;
}

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

int main(){
 int a,b;
 
 while(1){
  cin >> a >> b;
  if(a==0&&b==0)break;
  if(a<b) cout << a <<" "<< b << endl;
  else cout << b <<" "<< a << endl;
 }

 return 0;
}

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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++) 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = INF + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 21;

int n;
int a[N][N];

bool read () {
	if (scanf("%d", &n) != 1)
		return false;
	forn(i, n) forn(j, n)
		scanf("%d", &a[i][j]);
	return true;
}

int dp[1 << N][N];

int calc(int mask, int v){
	if (v == n) 
		return 1;
	if (dp[mask][v] != -1)
		return dp[mask][v];
	dp[mask][v] = 0;
	forn(u, n) if (!((mask >> u) & 1) && a[v][u])
		dp[mask][v] = (calc(mask ^ (1 << u), v + 1) + dp[mask][v]) % MOD;
	return dp[mask][v];
}

void solve(){
	memset(dp, -1, sizeof(dp));
	printf("%d\n", calc(0, 0));
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int tt = clock();
	
#endif
	
	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;

	while(read()) {	
		solve();
		
#ifdef _DEBUG
	cerr << "TIME = " << clock() - tt << endl;
	tt = clock();
#endif

	}
}

Measured memory_bytes: 172416
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int INF = 1e8;

int white[10][1005]; // そのグループにwhiteチョコがいくつあるか

int main() {
  // H <= 10なので縦だけbit全探索
  int H, W, K;
  cin >> H >> W >> K;
  vector<string> S(H);
  rep(i, H) cin >> S[i];
  int ans = 100005;
  for (int bit = 0; bit < (1<<(H-1)); bit++) {
    int group = 0;
    vector<int> id(H);
    rep(i, H) {
      id[i] = group;
      if (bit>>i & 1) group++;
    }
    group++;  // 縦のグループ数
    rep(i, group) rep(j, W) white[i][j] = 0;
    rep(i, H) rep(j, W) if (S[i][j] == '1') white[id[i]][j]++;
    int temp = group - 1;
    vector<int> cur(group);
    auto add = [&](int j) {
      rep(k, group) cur[k] += white[k][j];
      rep(k, group) if (cur[k] > K) return false; 
      return true;
    };
    rep(j, W) {
      if (!add(j)) {
        temp++;
        cur = vector<int> (group);
        if (!add(j)) {
          temp = INF;
          break;
        }
      }
    }
    ans = min(ans, temp);
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
using namespace std;

int main(){
  int n, m, s;
  while(scanf("%d%d", &n, &m) && n && m){
    vector<int>t(n); 
    vector<int>h(m);
    bool f = false;
    int sum = 0, taro = 0, hanako = 0;
    rep(i, n) scanf("%d", &s), t[i] = s, taro += s,sum += s;
    rep(i, m) scanf("%d", &s), h[i] = s, hanako += s,sum += s;
    //    printf("%d %d %d\n", taro, hanako, sum);
    //    rep(i, n) printf("%d ", t[i]); puts("");
    //    rep(i, m) printf("%d ", h[i]); puts("");
    taro -= (sum / 2);
    int res[2] = {99999, 99999};
    rep(i, n) rep(j, m){
      if(t[i] - h[j] == taro && res[0]+res[1] > t[i]+h[j]){
	res[0] = t[i], res[1] = h[j];
	f = true;
	//	printf("%d %d\n", t[i], h[j]);
      }
    }
    if(sum % 2) f = false;    
    printf(f?"%d %d\n":"-1\n", res[0], res[1]);
  }
  return 0;
}

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

int gcd(int a, int b) {
    while (b > 0) {
        int t = a; a = b; b = t % b;
    }
    return a;
}

int main(int argc, char** argv) {
    int n, m; cin >> n >> m;
    string s, t; cin >> s >> t;
    int g = gcd(m, n);
    for (long long a = 0; a < s.size(); a++) {
        if (a * m % n == 0) {
            int b = a * m / n;
            if (s[a] != t[b]) {
                cout << "-1\n";
                return 0;
            }
        }
    }
    cout << (long long)m * n / g << endl;
}


Measured memory_bytes: 764
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import groupby
    s = input()
    ans = len(list(groupby(s))) - 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 83812