akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    int s, c;
    int vis[N+1]; fill(vis, vis + N + 1, -1);
    int ans = 0;
    for(int i=0; i<M; i++){
        cin >> s >> c;
        if(s == 1 && c == 0 and N != 1){
            ans = -1;
            break;
        }
        if(vis[s] == -1){
            ans += pow(10, N - s) * c;
        }
        else{
            if(vis[s] != c){
                ans = -1;
                break;
            }
        }
        vis[s] = c;
    }
    if(ans < 0) cout << ans << endl;
    else{
        if(ans < pow(10, N - 1) && N != 1){
            ans += pow(10, N - 1);
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

#define XDIR 0
#define YDIR 1

lli data[2010][2010];
lli cnt[2][2010][2010];

lli calc(lli dir,lli startY,lli startX,lli nowY,lli nowX){
	lli dx[2]={1,0};
	lli dy[2]={0,1};
	if(data[nowY][nowX]==-1){
		cnt[dir][nowY][nowX] = abs(nowY-startY) + abs(nowX - startX);
	}

	if(cnt[dir][nowY][nowX])return cnt[dir][nowY][nowX];

	return cnt[dir][nowY][nowX]=calc(dir,startY,startX,nowY+dy[dir],nowX+dx[dir]);
}

signed main(){

	lli h,w;
	cin>>h>>w;

	REP(k,0,2)REP(i,0,2010)REP(j,0,2010){
		data[i][j]=-1;
		cnt[k][i][j]=0;
	}

	REP(i,1,h+1)REP(j,1,w+1){
		char tmp;
		cin>>tmp;
		if(tmp=='.'){
			data[i][j]=0;
		}
	}
	lli ans=0;

	for(lli i=1;i<=h;i++){
		for(lli j=1;j<=w;j++){
			lli sum=0;
			if(data[i][j]==0){
				lli flag=0;
				for(lli k=0;k<2;k++){
					sum+=calc(k,i,j,i,j);
					if(calc(k,i,j,i,j))flag++;
				}
				if(flag==2)sum-=1;
			}
			if(DEBUG)cout<<sum<<" ";
			ans=max(ans,sum);
		}
		if(DEBUG)cout<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 95104
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s,t;
  cin>>s>>t;
  int n=s.length(),x=0;
  for(int i=0;i<n;i++){
    if(s[i]!=t[i])
      x++;
  }
  cout<<x;
}

Measured memory_bytes: 3932
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int Q, doubles, lengths, dat[1000009], tmp[1000009], arrays[1000009]; string S, T;
bool compare_suffix(int i, int j) {
	if (dat[i] == dat[j]) {
		int ri = (i + doubles <= lengths ? dat[i + doubles] : -1);
		int rj = (j + doubles <= lengths ? dat[j + doubles] : -1);
		return ri < rj;
	}
	return dat[i] < dat[j];
}
void suffix_array() {
	lengths = S.size();
	for (int i = 0; i <= lengths; i++) arrays[i] = i, dat[i] = i < lengths ? S[i] : -1;
	for (doubles = 1; doubles <= lengths; doubles <<= 1) {
		sort(arrays, arrays + lengths + 1, compare_suffix);
		tmp[arrays[0]] = 0;
		for (int i = 1; i <= lengths; i++) tmp[arrays[i]] = tmp[arrays[i - 1]] + (compare_suffix(arrays[i - 1], arrays[i]) ? 1 : 0);
		for (int i = 0; i <= lengths; i++) dat[i] = tmp[i];
	}
}
int main() {
	cin >> S >> Q;
	suffix_array();
	for (int i = 0; i < Q; i++) {
		cin >> T;
		int l = 0, r = S.size() + 1, f = 0;
		while (r - l > 1) {
			int m = (l + r) / 2;
			string S1 = S.substr(arrays[m], T.size());
			if (S1 == T) { f = 1; break; }
			if (S1 < T) l = m;
			else r = m;
		}
		printf("%d\n", f);
	}
}

Measured memory_bytes: 15840
#include <iostream>
#include <string>
#include <cstring>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#define int long long
#define INF 1000000007
using namespace std;
signed main(){
    double w,h;
    cin>>w>>h;
    double x,y;
    cin>>x>>y;
    double a=w/2;
    double b=h/2;
    cout << fixed << setprecision(16);
    double ans=w*h/2;
    cout<<ans<<endl;
    if(a==x&&b==y)cout<<1<<endl;
    else cout<<0<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
 int r ,d,x;
  cin >> r >> d >> x;
  vector<int> da(11,x);
  for(int i=0;i<10;i++){
    da[i+1]=da[i]*r-d;
}
  for(int i=1;i<11;i++){
    cout << da[i] << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <queue>

using namespace std;

int main() {
  string max_word;
  map<string, int> m;
  string str;
  while (cin >> str) {
    m[str]++;
    if (str.size() > max_word.size()) max_word = str;
  }
  priority_queue<pair<int, string> > que;
  for (map<string, int>::iterator it = m.begin() ; it != m.end(); it++) {
    que.push(pair<int, string>(it->second, it->first));
  }
  cout << que.top().second << ' ' << max_word << endl;

  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
using namespace std;

/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long ll;

#define fi first
#define se second

using Graph = vector<vector<int>>;

void dfs(vector<vector<int>> &ab, vector<bool> &visited, int index, int n)
{
    for (auto v : ab[index])
    {
        if (visited[v] == false)
        {
            visited[v] = true;
            dfs(ab, visited, v, n);
        }
    }
}

int main()
{
    ll x;
    cin >> x;
    for (ll a = 0; a <= 1000000000; a++)
    {
        if (pow(a, 5) - x < 0)
        {
            for (ll b = 0; b >= -1000000000; b--)
            {
                if (pow(a, 5) - x == pow(b, 5))
                {
                    cout << a << " " << b << endl;
                    return 0;
                }
                if (pow(a, 5) - x > pow(b, 5))
                {
                    break;
                }
            }
        }
        else if (pow(a, 5) - x == 0)
        {
            cout << a << " " << 0 << endl;
            return 0;
        }
        else
        {
            for (ll b = 0; b <= 1000000000; b++)
            {
                if (pow(a, 5) - x == pow(b, 5))
                {
                    cout << a << " " << b << endl;
                    return 0;
                }
                if (pow(a, 5) - x < pow(b, 5))
                {
                    break;
                }
            }
        }
    }

    return 0;
}


Measured memory_bytes: 4104
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
long h,m,s,r,r1,r2,r3;
while(cin>>h){
cin>>m>>s;
if(h==-1)break;
r=7200-h*3600-m*60-s;
r1=r/3600;
r2=(r-r1*3600)/60;
r3=r-r1*3600-r2*60;
printf("%02d:%02d:%02d\n",r1,r2,r3);
r*=3;
r1=r/3600;
r2=(r-r1*3600)/60;
r3=r-r1*3600-r2*60;
printf("%02d:%02d:%02d\n",r1,r2,r3);
}
return 0;
}

Measured memory_bytes: 1160
import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())

    w = [0 for i in range(n)]
    v = [0 for i in range(n)]
    for i in range(n):
        a, b = map(int, input().split(","))
        v[i] = a
        w[i] = b

    dp = [[0 for j in range(w_max + 1)] for i in range(n + 1)]
    for i in range(n)[::-1]:
        for j in range(w_max + 1):
            if j < w[i]:
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i])
    print("Case ",case,":",sep="")
    print(max(dp[0]))
    print(dp[0].index(max(dp[0])))



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

int main() {
  int n,s;
  cin >> n;
  s = 0;
  long long x =0;
  vector<int> a(n),b(n);
  for(int i = 0 ; i < n ; i++){
    cin >> a.at(i);
    if(a.at(i) < 0){
      b.at(i) = -a.at(i);
      s++;
    }
    else {
      b.at(i) = a.at(i);
    }
  }
  
  sort(b.begin(), b.end());
  for(int i = 0 ; i<n ; i++){
    x += b.at(i);
  }
    
  if(s%2 == 0){
    cout << x << endl;
  }
  else {
    cout << x -2*b.at(0) << endl;
  }
}
  


Measured memory_bytes: 1024
def f(n):
    if n<=0: return 0
    if n%2==1:
        a = (n+1)//2
        if a%2==0: return 0
        else: return 1
    else:
        a = n//2
        if a%2==0: return n
        else: return n+1
A,B = map(int,input().split())
print(f(A-1)^f(B))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define llint long long int
#define ldouble long double

using namespace std;

int main() {
    vector<llint> tra(5);
    llint N;
    cin>>N;
    for(int i=0;i<5;i++){
        cin>>tra.at(i);
    }

    llint min=tra.at(0);
    llint sum=0;

    for(int i=1;i<5;i++){
        if(min>tra.at(i)){
            min=tra.at(i);
        }
    }

    if(N<=min){
        sum=5;
    }
    else if(N%min==0){
        sum=4+N/min;
    }
    else{
        sum=5+N/min;
    }

    cout<<setprecision(100)<<sum<<endl;
return 0;
}

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

int main() {
	int A, B;
  cin >> A >> B;
  
  vector<vector<char>> S(A, vector<char>(B, '.'));

  for (int i = 0; i < A; i++) {
    for (int j = 0; j < B; j++) {
      cin >> S.at(i).at(j);
    }
  }
  
  const vector<int> dx = {1, 0, -1, 0, 1, -1, -1, 1};
  const vector<int> dy = {0, 1, 0, -1, 1, 1, -1, -1};
  
  for (int i = 0; i < A; i++) {
    for (int j = 0; j < B; j++) {
      int count = 0;
      if( S.at(i).at(j) == '#' ) continue;
      
      int num = 0;
      for(int d = 0; d < 8; d++){
        const int ni = i + dy.at(d);
        const int nj = j + dx.at(d);

        if (ni < 0 or A <= ni) continue;
        if (nj < 0 or B <= nj) continue;
        if (S.at(ni).at(nj) == '#') num++;
      }
      S.at(i).at(j) = char(num + '0');
    }
  }
  
  for (int i = 0; i < A; i++) {
    for (int j = 0; j < B; j++) {
      cout << S.at(i).at(j);
      if (j == B-1) cout << endl;
    }
  }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
  public static void main(String[] args){
    FastScanner fs = new FastScanner();
    long num1 = fs.nextLong();
    long num2 = fs.nextLong();
    if( (num1+num2)%3 == 0||num1%3 == 0||num2%3 == 0) System.out.println("Possible");
    else{ System.out.println("Impossible");}

  }
}
class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(String s) {
			try {
				br = new BufferedReader(new FileReader(s));
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}

		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String nextToken() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		String nextLine(){
			String line = "";
			try{
				line = br.readLine();
			}catch(IOException e){
				e.printStackTrace();
			}
			return line;
		}

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

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

		double nextDouble() {
			return Double.parseDouble(nextToken());
		}
	}


Measured memory_bytes: 21204
#include <iostream>

using namespace std;

int main() {
  int a, b;
  char op;
  for (;;) {
    cin >> a >> op >> b;
    if (op == '?')
      break;
    int n;
    switch (op) {
      case '+':
        n = a + b;
        break;
      case '-':
        n = a - b;
        break;
      case '*':
        n = a * b;
        break;
      case '/':
        n = a / b;
        break;
    }
    cout << n << endl;
  }
  return 0;
}

Measured memory_bytes: 3072
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if sum(a) < sum(b):
    print(-1)
else:
    d = [a[i] - b[i] for i in range(n)]
    count = 0
    num = 0
    for i in d:
        if i < 0:
            count += 1
            num += i
    d.sort(reverse = True)
    for i in d:
        if num >= 0:
            break
        num += i
        count += 1
    print(count)

Measured memory_bytes: 24288
s = input()
n = len(s)
rem = 0
ans = 0

for i in range(n):
    if s[i]=="g":
        if rem:
            ans +=1
            rem -=1
        else:
            rem +=1
    else:
        if rem:
            rem -=1
        else:
            ans -=1
            rem +=1
print(ans)

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

using namespace std;

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

	map<string, int> a;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		a[s]++;
	}

	cout << "AC x " << a["AC"] << endl;
	cout << "WA x " << a["WA"] << endl;
	cout << "TLE x " << a["TLE"] << endl;
	cout << "RE x " << a["RE"] << endl;

	return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

int a, b;

int main() {
    scanf("%d%d", &a, &b);
    if ((a+b)%2) {
        puts("IMPOSSIBLE");
    } else {
        printf("%d\n", (a+b)/2);
    }
}


Measured memory_bytes: 256
x,y=map(int,input().split())
a=-1
p=10**9+7
for i in range(x//2+1):
  if i+2*(x-2*i)==y:
    a=i
    break
if a==-1:
  print(0)
  exit()
elif a==0:
  print(1)
else:
  gyaku=[0,1]
  for i in range(2,a+1):
    gyaku.append(((p//i)*-gyaku[p%i])%p)
  com=[1]
  for i in range(1,a+1):
    com.append(com[-1]*gyaku[i]*(x-a+1-i)%p)
  print(com[-1])  


Measured memory_bytes: 35496
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

template<typename T>
struct SegmentTree{
private:
    int N;
    vector<T> node;
    function<T(T, T)> F;
    T E;
public:
    void init(int n, function<T(T, T)> f, T e, T def){
        F = f;
        E = e;
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, e);
        for(int i=0; i<n; i++) node[N-1+i] = def;
        for(int i=N-2; i>=0; i--) node[i] = F(node[(i<<1)+1], node[(i<<1)+2]);
    }
    T& operator [](int a){
        return node[N-1+a];
    }
    void update(int a, T x){
        a += N-1;
        node[a] = x;
        while(a > 0){
            a = (a-1)>>1;
            node[a] = F(node[(a<<1)+1], node[(a<<1)+2]);
        }
    }
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        if(b <= l || r <= a) return E;
        if(a <= l && r <= b) return node[k];
        return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
    }
};

int H, W;
int M;

vector<int> v[300000];
SegmentTree<int> st;
int ans = 0;

signed main(){
    cin >> H >> W;
    cin >> M;
    st.init(H, [](int a, int b){ return max(a, b); }, 0, 0);
    rep(i, M){
        int y, x;
        cin >> y >> x;
        v[x-1].pb(y-1);
        st.update(y-1, st[y-1]+1);
    }

    rep(i, W){
        rep(j, v[i].size()){
            st.update(v[i][j], st[v[i][j]]-1);
        }
        ans = max(ans, (int)v[i].size() + st.query(0, H));
        rep(j, v[i].size()){
            st.update(v[i][j], st[v[i][j]]+1);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 23832
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline().strip()

def solve(N: int, M: int, p: "List[int]", S: "List[str]"):
    solved = [False for i in range(N + 1)]
    penalties = [0 for i in range(N + 1)]
    for prob, verd in zip(p, S):
        if not solved[prob]:
            penalties[prob] += verd == 'WA'
            solved[prob] = verd == 'AC'
    print(sum(solved), sum(penalty for i, penalty in enumerate(penalties) if solved[i]))
    return

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
    M = int(next(tokens))  # type: int
    p = [int()] * (M)  # type: "List[int]"
    S = [str()] * (M)  # type: "List[str]"
    for i in range(M):
        p[i] = int(next(tokens))
        S[i] = next(tokens)
    solve(N, M, p, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 53724
M=998244353;
char S[4000];
d[4001][4001];
x,y;
i,j,k;
main(){
	gets(S);
	for(**d=1;i<2*strlen(S);++i)
		for(S[i]?y=2*i+2-(x+=S[i]-48):0,j=0;j<=i;++j)
			for(k=0;k<2;++k)
				d[j+!k][i-j+k]+=j-k<x&&i-j+k<=y?d[j][i-j]%M:0;
	printf("%d",d[x][y]%M);
}


Measured memory_bytes: 61952
import sys
sys.setrecursionlimit(10**9)

def main():
    S = input()
    N = len(S)
    MOD = 10**9+7

    # S = [int(s) if s!="?" else -1 for s in S ]
    dp = [[0] * 13 for _ in range(N+1)]

    s = S[0]
    if s == "?":
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][int(s)%13] += 1
    for i in range(1,N):
        s = S[i]
        if s == "?":
            for j in range(0,13):
                for x in range(10):
                    k = (j*10+x)%13
                    dp[i][k] += dp[i-1][j]
                    dp[i][k] %= MOD
        else:
            for j in range(0,13):
                k = (j*10+int(s))%13
                dp[i][k] += dp[i-1][j]
                dp[i][k] %= MOD


    print(dp[N-1][5])


if __name__ == "__main__":
  main()

Measured memory_bytes: 61916
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();
    List<Integer> list = new ArrayList<>();
    boolean b = false;

    for (int i = 0; i < N; i++) {
      int A = sc.nextInt();
      if (A % 2 == 0) {
        if ((A % 3 != 0) && (A % 5 != 0)) {
          b = true;
          break;
        }
      }
    }

    if (!b) {
      System.out.println("APPROVED");
    } else {
      System.out.println("DENIED");
    }


    sc.close();
  }
}

Measured memory_bytes: 23380
#include <iostream>
#include <algorithm>

using namespace std;

main(){
  int data1[10], data2[10];
  while(cin >> data1[0]){
    for(int i=1;i<10;i++){
      cin >> data1[i];
    }
    for(int i=0;i<10;i++){
      cin >> data2[i];
    }

    sort(data1, data1+10);
    sort(data2, data2+10);
    cout << data1[7]+data1[8]+data1[9] << ' ';
    cout << data2[7]+data2[8]+data2[9] << endl;
  }
  return 0;
}

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

const int MOD = 998244353;

vector<int> ten;
int nine_inverse = 443664157;

int power(int a, int b) {
	if (b == 0) return 1;
	int result = power(a, b / 2);
	return (ll) result * result % MOD * (b % 2 == 1 ? a : 1) % MOD;
}

int f(int d, int length) {
	return (ll) (ten[length] - 1) * nine_inverse % MOD * d % MOD;
}

class segment {
public:
	int n;
	vector<int> tree, lazy;

	segment(int n) {
		this->n = n;
		tree.resize(4 * n);
		lazy.resize(4 * n, -1);
	}

	void propagate(int v, int l, int r) {
		if (lazy[v] == -1) return;

		int d = lazy[v];
		int mid = (l + r) / 2;
		tree[2 * v] = f(d, mid - l);
		tree[2 * v + 1] = f(d, r - mid);
		lazy[2 * v] = d;
		lazy[2 * v + 1] = d;

		lazy[v] = -1;
	}
	
	void update(int p, int q, int d, int l, int r, int v) {
		if (q <= l || p >= r)
			return;
		if (p <= l && r <= q) {
			int length = r - l;
			tree[v] = f(d, length);
			lazy[v] = d;
			return;
		}

		propagate(v, l, r);

		int mid = (l + r) / 2;
		update(p, q, d, l, mid, 2 * v);
		update(p, q, d, mid, r, 2 * v + 1);
		tree[v] = ((ll) ten[r - mid] * tree[2 * v] % MOD + tree[2 * v + 1]) % MOD;
	}

	void update(int p, int q, int d) {
		update(p, q, d, 0, n, 1);
	}
};

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

	ten.resize(n + 1);
	ten[0] = 1;
	for (int i = 1; i <= n; i++) {
		ten[i] = (ll) 10 * ten[i - 1] % MOD;
	}

	segment tree(n);
	tree.update(0, n, 1);
	for (int i = 0; i < q; i++) {
		int l, r, d;
		cin >> l >> r >> d;
		l--;
		tree.update(l, r, d);
		cout << tree.tree[1] << '\n';
	}
	return 0;
}

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

public class Main{

	static Scanner s=new Scanner(System.in);

	public static void main(String __[]){
		input();
		solve();
	}

	static int h, w, n, k, f[][];

	private static void input(){
		h=s.nextInt();
		w=s.nextInt();
		n=s.nextInt();
		k=s.nextInt();
		f=new int[h][w];
	}

	private static void solve(){
		// loop:
		for(int i=0; i<h; i++){
			int rowsum=question(i,0,i,w-1);
			for(int j=0; j<w-2&&rowsum!=0; j+=4){
				int buf=question(i,j,i,j+3);
				rowsum-=buf;
				switch(buf){
				case 0:
					break;
				case 1:
					buf=question(i,j  ,i,j+1)==0?j+2:j  ;
					f[i][buf  ]=question(i,buf,i,buf);
					f[i][buf+1]=1-f[i][buf];
					break;
				case 2:
					buf=question(i,j,i,j+1);
					switch(buf){
					case 0:
						f[i][j  ]=0;
						f[i][j+1]=0;
						f[i][j+2]=1;
						f[i][j+3]=1;
						break;
					case 1:
						f[i][j  ]=question(i,j  ,i,j  );
						f[i][j+1]=1-f[i][j  ];
						f[i][j+2]=question(i,j+2,i,j+2);
						f[i][j+3]=1-f[i][j+2];
						break;
					case 2:
						f[i][j  ]=1;
						f[i][j+1]=1;
						f[i][j+2]=0;
						f[i][j+3]=0;
						break;
					}
					break;
				case 3:
					if(question(i,j  ,i,j+1)==2){
						f[i][j  ]=1;
						f[i][j+1]=1;
						f[i][j+2]=question(i,j+2,i,j+2);
						f[i][j+3]=1-f[i][j+2];
					}else{
						f[i][j  ]=question(i,j  ,i,j  );
						f[i][j+1]=1-f[i][j  ];
						f[i][j+2]=1;
						f[i][j+3]=1;
					}
					break;
				case 4:
					f[i][j  ]=1;
					f[i][j+1]=1;
					f[i][j+2]=1;
					f[i][j+3]=1;
					break;
				}
			}
			if(h%4!=0&&rowsum>0){
				f[i][w-2]=question(i,w-2,i,w-2);
				rowsum-=f[i][w-2];
				f[i][w-1]=rowsum;
			}
		}

		long pow=1, result=0;
		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++){
				result+=f[i][j]*pow;
				result%=k;
				pow*=2;
				pow%=k;
			}
		}

		//Arrays.stream(f).map(Arrays::toString).forEach(System.out::println);

		answer(result);
	}

	private static final int question(int x1, int y1, int x2, int y2){
		System.out.printf("? %d %d %d %d\n",x1,y1,x2,y2);
		return s.nextInt();
	}

	private static final void answer(long a){
		System.out.printf("! %d\n",a);
	}
}


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

int main() {
  long long x, a, b;
  cin >> x;
  a = x / 500;
  x -= a * 500;
  b = x / 5;
  cout << a * 1000 + b * 5 << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<math.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int>nums;
  int min = 150;
  int max = -150;
  while(n--){
  	int c;
    cin >> c;
    nums.push_back(c);
    
    if(c<min)min=c;
    if(c>max)max=c;  
  }
  int cost = 1000000000;
  while(min<=max){
    int temp_cost = 0;
  	for(int i=0;i<nums.size();++i){
    	int sq = pow(nums[i]-min,2);
      	temp_cost+=sq;
    }
    if(temp_cost<cost)cost=temp_cost;
    min++;
  }
  cout << cost << endl;
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    // Your code here!
    int K,T;
    cin >> K >> T;
    int v[1000];
   long long int S=0;
    int maxx=-1;
    for(int i=0;i<T;i++){
        int x;
        cin>>x;
        v[i]=x;
        maxx=max(maxx,x);
        S+=x;
    
    }
    S-=maxx;
    //cout << S << " "  <<maxx;
    if(S+1>=maxx)
       cout << 0;
       else {
           cout << maxx-S-1;
       }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		ans^=x;
	}
	if(ans==0) puts("Yes");else puts("No");
	return 0;
}

Measured memory_bytes: 256
N = int(input())
d = {}
for i in range(2, N + 1):
	m = i
	for j in range(2, i + 1):
		if m == 1:
			break
		while m % j == 0:
			if j in d:
				d[j] = d[j] + 1
			else:
				d[j] = 1
			m = m / j
l = [3, 5, 15, 25, 75]
e = {}
for i in l:
	e[i] = 0
for i in d:
	for j in l:
		if d[i] > j - 2:
			e[j] += 1
ans = 0
if e[5] > 1 and e[3] > 2:
	ans = int(e[5] * (e[5] - 1) / 2 * (e[3] - 2))
if e[3] > 1 and e[25] > 0:
	ans += e[25] * (e[3] - 1)
if e[5] > 1 and e[15] > 0:
	ans += e[15] * (e[5] - 1)
if e[75] > 0:
	ans += e[75]
print(ans)

Measured memory_bytes: 39024
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;

#define DE 1
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
#define ALL(s) (s).begin(),(s).end()
#define REP(i,n) for (int i = 0; i < (int)(n); ++i)
#define EACH(i,s) for (typeof((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl

template<class T1, class T2> ostream& operator<<(ostream &s, pair<T1,T2> P){return s<<'<'<<P.first<<", "<<P.second<<'>';}
template<class T> ostream& operator<<(ostream &s, vector<T> P) {s<<"{ ";for(int i=0;i<P.size();++i){if(i>0)s<<", ";s<<P[i];}return s<<" }"<<endl;}
template<class T1, class T2> ostream& operator<<(ostream &s, map<T1,T2> P) {s<<"{ ";for(typeof(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<'<'<<it->first<<"->"<<it->second<<'>';}return s<<" }"<<endl;}
template<class T> ostream& operator<<(ostream &s, set<T> P) {s<<"{ ";for(typeof(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<*it;}return s<<" }"<<endl;}



int n;
bool sch[35][55];
ll dp[55];

int main() {
    //freopen( "/Users/macuser/Documents/Programming/Contest/input.in", "r", stdin );
    
    while (cin >> n) {
        if (n == 0) break;
        
        memset(sch, 0, sizeof(sch));
        for (int i = 0; i < n; ++i) {
            int f; cin >> f;
            for (int j = 0; j < f; ++j) {
                int t; cin >> t;
                sch[t][i] = true;
            }
        }
        
        for (int i = 0; i < 55; ++i) dp[i] = (1LL<<i);
        
        int res = 100;
        for (int day = 1; day <= 30; ++day) {
            ll next = 0;
            for (int i = 0; i < n; ++i) {
                if (sch[day][i]) next |= dp[i];
            }
            
            if (next == (1LL<<n)-1) {
                res = day;
                break;
            }
            
            for (int i = 0; i < n; ++i) {
                if (sch[day][i]) {
                    dp[i] = next;
                }
            }
        }
        
        if (res < 100) cout << res << endl;
        else cout << -1 << endl;
    }
    
    return 0;
}


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

int main() {
  ll n; string s; cin >> n >> s;
  ll sum = 0;
  for(ll i = 1; i<=n; i++){
    if(s[i]!=s[i-1]) sum++;
  }
  cout << sum << endl;
    
  
  return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

// DP 動的計画法
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = Integer.parseInt(scanner.next());

        int[][] abc = new int[N][3];
        for (int i = 0; i < N; i++) {
            abc[i][0] = Integer.parseInt(scanner.next());
            abc[i][1] = Integer.parseInt(scanner.next());
            abc[i][2] = Integer.parseInt(scanner.next());
        }

        scanner.nextLine();

        // dp[i]: i日噛んで得られる幸福度の最大
        long[][] dp = new long[N + 1][3];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (j == k) continue;
                    dp[i + 1][k] = Math.max(dp[i + 1][k], dp[i][j] + abc[i][k]);
                }
            }
        }

        long ans = 0;
        for (int i = 0; i < 3; i++) {
            ans = Math.max(ans, dp[N][i]);
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 66852
import bisect
n=int(input())
s=input()
t=[[] for i in range(10)]
for i in range(n):
    t[int(s[i])].append(i)
c=0
for i in range(10):
    if len(t[i])==0:
        continue
    for j in range(10):
        if len(t[j]) == 0:
            continue
        m=bisect.bisect(t[j],t[i][0])
        if len(t[j])==m:
            continue
        for k in range(10):
            if len(t[k]) == 0:
                continue
            n=bisect.bisect(t[k],t[j][m])
            if len(t[k])==n:
                continue
            else:
                c+=1
print(c)

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

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

const int mod = 1000000007;
const int Maxn = 100005;

int fac[Maxn], inv[Maxn];
int n, k;
int a[Maxn];
int res;

int toPower(int a, int p)
{
    int res = 1;
    while (p) {
        if (p & 1) res = ll(res) * a % mod;
        p >>= 1; a = ll(a) * a % mod;
    }
    return res;
}

int Inv(int x) { return toPower(x, mod - 2); }

int C(int n, int k)
{
    if (n < 0 || k < 0 || k > n) return 0;
    return ll(fac[n]) * inv[k] % mod * inv[n - k] % mod;
}

void Solve()
{
    vector <ii> seq;
    for (int i = 0; i < n; i++)
        seq.push_back(ii(a[i], i));
    sort(seq.rbegin(), seq.rend());
    for (int i = 0; i < seq.size(); i++) {
        int ind = seq[i].second;
        int ways = ll(C(n - 1 - i, k - 1)) * seq[i].first % mod;
        if (ways < 0) ways += mod;
        res = (res + ways) % mod;
    }
}

int main()
{
    fac[0] = inv[0] = 1;
    for (int i = 1; i < Maxn; i++) {
        fac[i] = ll(i) * fac[i - 1] % mod;
        inv[i] = Inv(fac[i]);
    }
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    Solve();
    for (int i = 0; i < n; i++)
        a[i] = -a[i];
    Solve();
    printf("%d\n", res);
    return 0;
}


Measured memory_bytes: 3172
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
static const int INF = 2000000000;



int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int ans = max(a*b, c*d);
  cout << ans << endl;
}

Measured memory_bytes: 256
N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
RUI = [0]
ALL = [0]

A.each do |a|
  RUI << RUI.last + [0, a].max
  ALL << ALL.last + a
end

ans = 0

0.upto(N - K) do |i|
  score = RUI[i] + [0, (ALL[i + K] - ALL[i])].max + (RUI[N] - RUI[i + K])

  ans = score if ans < score
end

puts ans


Measured memory_bytes: 12940
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<double, ll> P;
const double INF=2e18;
const double EPS=1e-10;
const ll MOD=1e9+7;
ll sx,sy,gx,gy;
ll N;
struct Circle{
    ll x,y;
    ll r;
}circle[1010];
struct Edge{
    ll to;
    double cost;
};
vector<Edge> edges[1010];
const ll S=1001;
const ll G=1002;
double minCost[1010];
int main(){
    cin>>sx>>sy>>gx>>gy>>N;
    for(ll i=0;i<N;i++){
        ll x,y,r;
        cin>>x>>y>>r;
        circle[i]=Circle{x,y,r};
    }
    double dist=hypot(sx-gx,sy-gy);
    //cout<<"s to g:"<<dist<<endl;
    edges[S].push_back(Edge{G,dist});
    for(ll i=0;i<N;i++){
        dist = max(0.0,hypot(circle[i].x-sx,circle[i].y-sy)-circle[i].r); 
        edges[S].push_back(Edge{i,dist});
        dist = max(0.0,hypot(circle[i].x-gx,circle[i].y-gy)-circle[i].r);
        edges[i].push_back(Edge{G,dist});
    }
    for(ll i=0;i<N;i++){
        for(ll j=i+1;j<N;j++){
            dist = max(0.0,hypot(circle[i].x-circle[j].x,circle[i].y-circle[j].y)-circle[i].r-circle[j].r);
            edges[i].push_back(Edge{j,dist});
            edges[j].push_back(Edge{i,dist});
            // cout<<dist<<" ";
        }
        // cout<<endl;
    }

    priority_queue<P,vector<P>,greater<P> > pq;
    pq.push(P(0,S));
    minCost[S]=0;
    for(ll i=0;i<N;i++){
        minCost[i]=INF;
    }
    minCost[G]=INF;
    while(!pq.empty()){
        ll nowV=pq.top().second;
        double nowCost=pq.top().first;pq.pop();
        if(nowCost-EPS>minCost[nowV])continue;
        for(auto e:edges[nowV]){
            double newCost=minCost[nowV]+e.cost;
            if(newCost+EPS < minCost[e.to]){
                minCost[e.to]=newCost;
                pq.push(P(minCost[e.to],e.to));
            }
        }
    }
    cout<<setprecision(10)<<minCost[G]<<endl;
    return 0;
}

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

int main(){
  ll N,M;
  cin>>N>>M;
  if(N>M) swap(N,M);
  if(N>=3) cout<<(N-2)*(M-2)<<endl;
  else if(N==2) cout<<"0"<<endl;
  else if(N==1&&M!=1) cout<<M-2<<endl;
  else cout<<"1"<<endl;
}



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

string s;
int n;
int a[110];
int b[110];
int ans = 1e9;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> s; n = s.size(); s = ' ' + s;

	for (char ch = 'a'; ch <= 'z'; ++ch) {
		int cnt = 0;
		memset(a, 0, sizeof a);
		for (int i = 1; i <= n; ++i) if (s[i] == ch) a[i] = 1, ++cnt;
		if (cnt == 0) continue;
		if (cnt == n) { ans = 0; continue; }
		
		int res = 0, len = n;
		while(cnt > 0 && len > 1) {
			cnt = 0;
			for (int i = 1; i <= len - 1; ++i) if (a[i] || a[i + 1]) b[i] = 1; else b[i] = 0, ++cnt;
			for (int i = 1; i <= len - 1; ++i) a[i] = b[i];
			--len;
			++res;
		}

		ans = min(ans, res);
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <queue>
#include <list>
#include <string>
#include <cstdlib>
#include <algorithm>
using namespace std;

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

	int F[50];

	F[0] = 1;
	F[1] = 1;

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

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


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
int main() {
  int a, b, c, x; cin >> a >> b >> c >> x;
  int count = 0;
  for(int i = 0; i <= a; i++) {
    for(int j = 0; j <= b; j++) {
      for(int k = 0; k <= c; k++) {
        if(500 * i + 100 * j + 50 * k == x) {
          count++;
        }
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3576
#include <iostream>
#include <fstream>

#include <cmath>

using namespace std;

int main(){
    int a,b,C;
    const double PI = acos(-1);
    double rad;

    cin >> a >> b >> C;
    rad = C * PI / 180;

    double S = 1./2 * b * a * sin(rad);
    double L = sqrt(a*a + b*b - 2.*a * b * cos(rad)) + a + b;
    double h = S * 2 / a;
    printf("%.5f\n%.5f\n%.5f\n",S,L,h);
    


    return 0;
}


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

int main() {
  int N,K;
  //int S;
  cin >> N >> K;
  //vector<int> l(N);

  /*for (int i=0; i<N; i++) {
    cin >> l[i];
  }*/
  
  double ans = max((N-K+1.0) / N,0.0);
  int now = K;
  int n2 = 2;
  while (K > 0) {
    K = (K+1)/2;
    if (K <= N) {
      ans += max((min(now,N+1)-K+0.0) / N,0.0) / n2;
    }
    
    now = K;
    if (K == 1) {
      break;
    }
    n2 *= 2;
  }
  printf("%.10f", ans);
  return 0;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

int main() {
  ll l = 2, r = 3;
  int k;
  cin >> k;
  vector<int> a(k);
  rep(i,k) cin >> a[i];
  reverse(a.begin(), a.end());
  rep(i,k) {
    l = (l+a[i]-1) / a[i] * a[i];
    r = (r+a[i]-1) / a[i] * a[i];
  }
  if (r <= l) cout << -1 << endl;
  else cout << l << ' ' << r-1 << endl;
  return(0);
}

Measured memory_bytes: 3760
N, D = [int(_) for _ in input().split()]
x = [[int(_) for _ in input().split()] for i in range(N)]
res = 0
for i in range(N):
  for j in range(i+1, N):
    dd = 0
    for k in range(D):
      dd += (x[i][k] - x[j][k]) ** 2
    dd **= 0.5
    res += dd.is_integer()
print(res)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main() {
  int h, w, k, ans = 0;
  cin >> h >> w >> k;
  vector<vector<char>> c(h, vector<char>(w));
  for (int i = 0; i < h; i++)
  {
    for (int j = 0; j < w; j++)
    {
      cin >> c[i][j];
    }
    
  }
  for (int tmp1 = 0; tmp1 < (1 << h); tmp1++)
  {
    for (int tmp2 = 0; tmp2 < (1 << w); tmp2++)
    {
      int kuro = 0;
      for (int i = 0; i < h; i++)
      {
        for (int j = 0; j < w; j++)
        {
          if ( ((tmp1 >> i)&1) == 0 && ((tmp2 >> j)&1) == 0 && c[i][j] == '#')
          {
            kuro++;
          }
          
        }
        
      }
      if (kuro == k)
      {
        ans++;
      }
      
    }
    
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int N;

int main(){

	int current_time = 0,x = 0,y = 0;

	scanf("%d",&N);

	int next_time,next_x,next_y,dist;

	for(int loop = 0; loop < N; loop++){

		scanf("%d %d %d",&next_time,&next_x,&next_y);

		dist = abs(x-next_x)+abs(y-next_y);

		if(dist > (next_time-current_time) || dist%2 != (next_time-current_time)%2){ //マンハッタン距離+2t秒後にのみ到達可能

			printf("No\n");
			return 0;
		}
		x = next_x;
		y = next_y;
		current_time = next_time;
	}

	printf("Yes\n");

	return 0;
}


Measured memory_bytes: 256
N,K = gets.split.map(&:to_i)
if N > K
    new_n = N-K
else
    new_n = N
end
base = 1.0/N
result = Array.new(N,base)
for i in 0..(new_n-1)
    point = i+1
    n = 0
    while point < K
        point *= 2
        n += 1
    end
    result[i] = base/(2.0**n)
end
puts result.inject(:+)

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

  int digit_sum(ll n){
    if(n < 10)  return n;
    return digit_sum(n/10) + n%10;
  }

int main() {
  string n; cin >> n;
  vector<ll> vec(n.size());
  rep(i, n.size()){
    if(n[i] == '0')
      vec[i] = 0;
    if(n[i] == '1')
      vec[i] = 1;
    if(n[i] == '2')
      vec[i] = 2;
    if(n[i] == '3')
      vec[i] = 3;
    if(n[i] == '4')
      vec[i] = 4;
    if(n[i] == '5')
      vec[i] = 5;
    if(n[i] == '6')
      vec[i] = 6;
    if(n[i] == '7')
      vec[i] = 7;
    if(n[i] == '8')
      vec[i] = 8;
    if(n[i] == '9')
      vec[i] = 9;
  }
  ll k=0;
  rep(i, n.size())
    k += vec[i];  
 // cout << k << endl;
  
  if(k%9==0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 5236
#include<iostream>
using namespace std;
int main()
{
    int n,m;
    bool a[1010][1010];
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char x;
            cin>>x;
            if(x=='.')a[i][j]=1;
            else a[i][j]=0;
        }
    long long f[1010][1010];
    memset(f,0,sizeof(f));
    f[1][1]=1,a[1][1]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j])
                f[i][j]=(f[i-1][j]+f[i][j-1])%1000000007;
    cout<<f[n][m]<<endl;
    return 0;
}

Measured memory_bytes: 9216
n,m = map(int,input().split())

C={}
acc=0
wac=0
for i in range(m):
    p0,s = input().split()
    
    p = int(p0)
    if p in C :
        if C[p]!=-1:
            C[p]+=1
    else:
        C[p]=1

    if s=="AC" and C[p]!=-1:
        acc+=1
        wac+=C[p]-1
        C[p]=-1
        

print( acc, wac )

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

typedef long long ll;

#define N 25
const ll INF = 1ll << 60;

int len;
int a[N], b[N], c[N], del[N];
ll res;

void Calc(int n)
{
	for (int i = 0; i < n; ++i)
	{
		del[i] = b[i] - c[i] * 10 + (i && c[i - 1]);
		if (del[i] < -9 || del[i] > 9) return;
	}
	for (int i = 0; i < n; ++i) if (del[i] + del[n - 1 - i] != 0) return;
	
	int cnt[N] = {0};
	for (int i = 0; i <= n - 1 - i; ++i) cnt[i] = 10 - abs(del[i]);
	if (del[0] <= 0) cnt[0]--;
	ll tmp = 1;
	for (int i = 0; i <= n - 1 - i; ++i) tmp = tmp * cnt[i];
	res += tmp;
}

void DFS(int k, int n)
{
	if (k == n)
	{
		Calc(n);
		return;
	}
	c[k] = 0; DFS(k + 1, n);
	if (k < n - 1) c[k] = 1, DFS(k + 1, n);
}

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

	ll D; cin >> D;
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	for (ll t = D; D ; D /= 10) b[len++] = D % 10;
	for (int i = len; i <= 18; ++i) DFS(0, i);
	cout << res << endl;
	
	
	return 0;
}


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

public class Main {

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int[] abc = {a, b, c};
        Arrays.sort(abc);

        boolean result = abc[0] == 5 && abc[1] == 5 && abc[2] == 7;

        System.out.println(result ? "YES" : "NO");
    }
}


Measured memory_bytes: 21844
import java.util.*;
import java.io.*;

public class Main{
	public static void main(String[] args)  throws IOException,NumberFormatException{
		try {
			FastScanner sc=new FastScanner();
			int a=sc.nextInt();
			int b=sc.nextInt();
			int c=sc.nextInt();
			boolean ans=false;
		    for(int i=1;i<100;i++) {
		    	if((a*i-c)%b==0) {
		    		ans=true;
		    	}
		    }
		    System.out.println(ans?"YES":"NO");
		}
		catch(Exception e) {
			return ;
		}
		
	}
	static final Random random=new Random();
	
	static void ruffleSort(int[] a) {
		int n=a.length;
		for(int i=0;i<n;i++) {
			int oi=random.nextInt(n),temp=oi;
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	public static int GCD(int a,int b) {
		if(b==0)
			return a;
		return GCD(b,a%b);
	}
	
	
	public static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try { 
                                      st=new StringTokenizer(br.readLine());				               
                              } catch (IOException e) {}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		
		long[] readLongArray(int n) {
			long[] a=new long[n];
			for(int i=0; i<n ; i++) a[i]=nextLong();
			return a;
		}
		
		String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
	}

}


Measured memory_bytes: 32760
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 50;
int bigo[5][5], vis[5][5], n;
pair<int, int> pos[150];
int main() {
	
	for(int i = 1; i <= 3; i++) {
		for(int j = 1; j <= 3; j++) {
			scanf("%d", &bigo[i][j]);
			pos[bigo[i][j]] = make_pair(i, j);
		}
	}
	
	cin >> n;
	int x;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &x);
		vis[pos[x].first][pos[x].second] = 1;
	}
	
	bool f = 0;
	for(int i = 1; i <= 3; i++) {
		if(vis[i][1] && vis[i][2] && vis[i][3]) f = 1;
		if(vis[1][i] && vis[2][i] && vis[3][i]) f = 1;
	}
	if(vis[1][1] && vis[2][2] && vis[3][3]) f = 1;
	if(vis[3][1] && vis[2][2] && vis[1][3]) f = 1;
	if(f) puts("Yes");
	else puts("No"); 
	return 0;
} 


Measured memory_bytes: 3188
import math
n=int(input())
for i in range(n):
    ax,ay,ar,bx,by,br=[float(i) for i in input().split()]
    ab=abs(math.sqrt(pow(ax-bx,2)+pow(ay-by,2)))
    if ar>ab and (ar-ab)>br:
        print(2)
    elif br>ab and(br-ab)>ar:
        print(-2)
    elif ab<=(ar+br):
        print(1)
    else:
        print(0)

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

int main(void)
{
    int n,x,t,count,time;
    scanf("%d %d %d",&n,&x,&t);
    
    if(n%x==0)
    {
        count = n/x;
        time = count*t;
    }
    
    else
    {
        count = n/x + 1;
        time = count*t;
    }
    
    printf("%d",time);
    return 0;
    
    
}


Measured memory_bytes: 2156
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()



int main() {
  int A, B, m;
  cin >> A >> B >> m;
  vector<int> a(A), b(B), x(m), y(m), c(m), set(m);
  rep(i, A) cin >> a[i];
  rep(i, B) cin >> b[i];
  rep(i, m) {
    cin >> x[i] >> y[i] >> c[i];
    x[i]--; y[i]--;
    set[i] = a[x[i]] + b[y[i]] - c[i];
  }
  sort(all(set));
  sort(all(a));
  sort(all(b));
  cout << min(set[0], a[0]+b[0]) << endl;
  return 0;
}

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

int main() {
	long long N, K;
	cin >> N >> K;
	K++;
	vector<long long>A(N);
	rep(i, N) cin >> A.at(i);
	vector<bool>reach(N, false);
	long long j = 0, num = 0;
	vector<int>B;
	B.push_back(0);
	while (!reach.at(j)) {
		reach.at(j) = true;
		j = A.at(j) - 1;
		B.push_back(j);
		num++;
	}
	long long breath = 1;
	vector<int>roop;
	rep(i, B.size() - 1) {
		if (B.at(i) == B.back()) {
			breath = B.size() - i - 1;
			for (int j = i; j < i + breath; j++) {
				roop.push_back(B.at(j));
			}
		}
	}
	if (K <= (num - breath)) {
		cout << B.at(K - 1) + 1 << endl;
		return 0;
	}
	K -= (num - breath);
	long long pos = (K % breath) - 1;
	if (pos == -1) pos += breath;
	cout << roop.at(pos) + 1 << endl;
}

Measured memory_bytes: 7152
#include "bits/stdc++.h"
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;*/
//#define int long long
#define fastr ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,a,b) for(int i = a; i < b; i++)
#define rrep(i,a,b) for(int i = (a-1); i >= b; i--) 
#define fi first
#define se second
#define tit(v,i,c) get<c>(v[i])
#define mt make_tuple 
#define pb push_back
#define mp make_pair
double jk=0.4;
#define power(x,y) pow(x,y)+jk
#define endl "\n"
#define mod 1000000007
#define N 1000000000
int in(){
int n;cin>>n;
return n;}
void _do_(){
		string s;cin>>s;
		if(s[1]=='R')cout<<"ABC"<<endl;
		else cout<<"ARC"<<endl;


}signed main(){fastr
//int tc=in();
int tc=1;
while(tc--)_do_();
cerr<<"Time elapsed:";
cerr<<1000*clock()/CLOCKS_PER_SEC<<" ms\n";
return 0;}

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

int main(){
  int N,K,ans;
  int p[100][100];
  int l[100];

  while(true){
    cin >> N;
    if(N == 0) break;

    int *M = new int[N];
    
    for(int i=0;i<N;++i){
      cin >> M[i];

    
      for(int ix=0;ix<M[i];++ix){
	cin >> p[i][ix];
      }
    }
    
    cin >> K;
    
    for(int i=0;i<K;++i)
      cin >> l[i];
    
    
    int cnt = 0;
    for(int i=0;i<N;++i){
      if(K>M[i]) continue;
      if(M[i] == 0) continue;
      
      bool w = true;
      for(int k=0;k<K;++k){
	for(int ix = 0; ix<M[i]; ++ix){
	  if(l[k] == p[i][ix]){
	    break;
	  }
	  if(ix == M[i] - 1) w = false;
	}
	if(!w) break;
      }
      
      if(w) {
	++cnt;
	ans = i;

      }
    }

    if(cnt == 1){
      cout << ans + 1 << endl;
    }else{
      cout << -1 << endl;
    }

    delete[] M;

  }
  
  return 0;
}



Measured memory_bytes: 3120