akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, n) for(long long i = 0; i < (long long)(n); i++)
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    rep(i, n + 1){
        rep(j, m + 1){
            if(i * j + (n - i) * (m - j) == k){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 3636
A, B, C = map(int, input().split())
ans = 0

D = [[], []]
D[A % 2].append(A)
D[B % 2].append(B)
D[C % 2].append(C)

D.sort(key=lambda a: len(a))

if len(D[-1]) == 2:
    ans += 1
    D[-1][0] += 1
    D[-1][1] += 1

    A, B, C = D[0][0], D[1][0], D[1][1]

mx = max(A, B, C)
ans += sum((mx - a) // 2 for a in (A, B, C))
print(ans)


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

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second

int A,B,C;

int main(){
	cin >> A >> B >> C;
	if(A+B>=C) cout << B+C <<endl;
	else cout << 1+2*B+A <<endl;
	return 0;
}

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

int main() {
    int n; cin >> n;
    string s;
    map<string, bool> m;
    
    cin >> s;
    char t = s.back();
    m[s] = true;
    for (int i = 1; i < n; i++) {
        cin >> s;
        if (m[s] or t!=s[0]) {
            puts("No");
            return 0;
        }
        m[s] = true;
        t = s.back();
    }
    puts("Yes");
}


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

typedef long long ll;
const ll MOD = 1e9+7;



int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int a,b;
    cin>>a>>b;

    int r=1;

    if(r>=b){
        cout<<0;
        return 0;
    }
    for(int i=1;;i++){
        r+=a-1;
        if(r>=b){
            cout<<i;
            return 0;
        }
    }



    return 0;
}


Measured memory_bytes: 256
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n, = map(int,readline().split())
*a, = map(int,readline().split())
*b, = map(int,readline().split())
b = b[::-1]

same = [i for i in range(n) if a[i] == b[i]]
if same:
    v = a[same[0]] # b を逆順にしたので、重なる値は一種類しかない。これを v とおく。
    notv = [i for i in range(n) if a[i]!=v and b[i]!=v] # どっちもvとかぶらない index
    if len(same) > len(notv):
        print("No")
        exit()
    for i,j in zip(same,notv):
        b[i],b[j] = b[j],b[i]

print("Yes")
print(*b)

Measured memory_bytes: 41328
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

dp_town = [0]*(n+1)
dp_town[0] = min(a[0],b[0])
b[0] = b[0] - min(a[0],b[0])
for i in range(1,n):
    if b[i-1] > 0:
        dp_town[i] = min(a[i],b[i-1])
        a[i] -= b[i-1]
        b[i-1] -= min(a[i],b[i-1])
    if a[i] > 0:
        dp_town[i] += min(a[i],b[i])
        b[i] -= min(a[i],b[i])
    if i == n-1 and b[i] > 0:
        dp_town[n] += min(a[n],b[i])

print(sum(dp_town))

Measured memory_bytes: 82148
#pragma GCC optimize("-O3")
#include <bits/stdc++.h>
using namespace std;
void Main();
#ifdef ConanYu
#include "local.hpp"
#else
#define debug(...) do { } while(0)
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  Main();
}
#endif

int dp[100000][28];
int cur[28];
void Main() {
  string s, t; cin >> s >> t;
  const int n = s.size(), m = t.size();
  memset(cur, 0xff, sizeof cur);
  for(int i = n - 1; i >= 0; i--) {
    cur[s[i] - 'a'] = i;
  }
  for(int i = n - 1; i >= 0; i--) {
    cur[s[i] - 'a'] = i;
    for(int j = 0; j < 26; j++) {
      dp[i][j] = cur[j];
    }
  }
  int idx = 0;
  long long times = 0;
  for(int i = 0; i < m; i++) {
    const int fd = dp[idx][t[i] - 'a'];
    if(fd == -1) {
      cout << "-1\n";
      return;
    }
    if(fd < idx) {
      times++;
    }
    idx = fd + 1;
    if(idx == n && i != m - 1) {
      idx = 0;
      times++;
    }
  }
  cout << (times * n + idx) << "\n";
}


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

int main() {
  int W,H,N;
  cin >> W >> H >> N;
  vector<int> x={0,W},y={0,H};
  
  int s,t,a;
  for(int i=0; i<N; i++){
    cin >> s >> t >> a;
    if(a==1 && x.at(0)<s){
      x.at(0)=s;
    }
    else if(a==2 && s<x.at(1)){
      x.at(1)=s;
    }
    else if(a==3 && y.at(0)<t){
      y.at(0)=t;
    }
    else if(a==4 && t<y.at(1)){
      y.at(1)=t;
    }
  }
  
  if(x.at(1)<=x.at(0) || y.at(1)<=y.at(0)){
    cout << 0 << endl;
  }
  else{
    cout << (x.at(1)-x.at(0))*(y.at(1)-y.at(0)) << endl;
  }
}

Measured memory_bytes: 256
dic={2:1, 3:2, 4:3, 5:4, 6:5, 7:6, 8:7, 9:8, 10:9, 11:10, 12:11, 13:12, 1:13}
a, b = map(int, input().split())
if dic[a] < dic[b]:
  print('Bob')
elif dic[b] < dic[a]:
  print('Alice')
else:
  print('Draw')

Measured memory_bytes: 3064
n = int(input())
a = []
for i in range(n):
    ai = int(input())
    a.append(ai)

lst = [a[0]]
for i in range(1, n):
    ai = a[i]
    left = -1
    right = len(lst)
    while left+1 < right:
        mid = (left + right) // 2
        if lst[mid] < ai:
            right = mid
        else:
            left = mid
    if right == len(lst):
        lst.append(ai)
    else:
        lst[right] = ai
print(len(lst))

Measured memory_bytes: 85964
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int main(void){
	          int i;

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

	          sort(v.begin(),v.end());
	          reverse(v.begin(),v.end());

	          ll x=0,y=0;
	          int p;
	          for(i=1;i<N;i++){
	        	  if(v[i]==v[i-1]){
	        		  x=v[i];
	        		  p=i+2;
	        		  break;
	        	  }
	          }
	          for(i=p;i<N;i++){
	        	  if(v[i]==v[i-1]){
	        		  y=v[i];
	        		  break;
	        	  }
	          }

	          cout << x*y << endl;

	          return 0;
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		long A = long.Parse(str[0]);
		long B = long.Parse(str[1]);
		var listA = PrimeFactors(A);
		var listB = PrimeFactors(B);
		long ans = 1;
		foreach(var a in listA){
			if(listB.Contains(a)){
				ans++;
			}
		}
		Console.WriteLine(ans);
	}
	
	public static HashSet<long> PrimeFactors(long n){
		long i = 2;
		long tmp = n;
		var list = new HashSet<long>();
		while(i*i<=n){
			if(tmp%i==0){
				tmp /= i;
				list.Add(i);
			} else {
				i++;
			}
		}
		if(tmp != 1){
			list.Add(tmp);
		}
		return list;
	}
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
long long int N,M,a;
cin >>N>>M; unsigned long long int S[N+2];
for(long long int i=1;i<N+1;i++){
S[i]=1;
}
S[2]=2;
for(long long int i=0;i<M;i++){
cin >> a;
S[a]=0;
}
if(S[1]==0&&S[2]!=0)S[2]=1;

for(long long int i=1;i<N-1;i++){
if(S[i+2]!=0)S[i+2]=S[i+1]+S[i];
S[i+2]%=1000000007;
}
cout <<S[N];

}


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

using namespace std;

int main(){
        string W; cin >> W;
        string T;
        int ans = 0;
        cin >> T;
        transform(W.begin(),W.end(),W.begin(),::toupper);
        transform(T.begin(),T.end(),T.begin(),::toupper);
        while (true) {
                if(W == T) ans++;
                cin >> T;
                if(T == "END_OF_TEXT") break;
                transform(T.begin(),T.end(),T.begin(),::toupper);
        }   
        cout << ans << endl;

return 0;
}

Measured memory_bytes: 3220
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")

#define fi first
#define se second
#define ep emplace
#define eb emplace_back
#define mp make_pair
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) 
#define rep2(i, n, m) for (ll i = n; i <= (ll)(m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (ll)(m); --i)

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007, MAX = 100001;

int n;
vector<vpi> edge(MAX);
int dst[MAX];

void dijkstra(int start)
{
  priority_queue<pi,vpi,greater<pi>> que;
  rep(i, MAX) dst[i] = 1e18;

  que.emplace(0, start);
  dst[start] = 0;

  while (!que.empty()) {
    auto p = que.top(); que.pop();
    int d = p.fi, from = p.se;

    if (dst[from] < d) continue;

    for (auto next : edge[from]) {
      int to = next.fi, dis = next.se;

      if (dst[to] > d + dis) {
        que.emplace(d + dis, to);
        dst[to] = d + dis;
      }
    }
  }
}

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  rep(i, n-1) {
    int a, b, c; cin >> a >> b >> c;
    edge[a-1].eb(b-1, c);
    edge[b-1].eb(a-1, c);
  }

  int q, k; cin >> q >> k;
  dijkstra(k-1);

  rep(i, q) {
    int x, y; cin >> x >> y;
    cout << dst[x-1] + dst[y-1] << endl;
  }

  return (0);
}


Measured memory_bytes: 13972
import Foundation

let input1: String = readLine()!
let N = Int(input1)!
let input2 = readLine()!
let bosses = input2.components(separatedBy: " ").map { Int($0)! }

var counts: [Int] = .init(repeating: 0, count: N)

for b in bosses {
  counts[b-1] += 1
}
for v in counts {
  print(v)
}

Measured memory_bytes: 20856
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 998244353
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}

int dp[3005][3005] = {};

signed main(void) {
    int n,s;
    cin >> n >> s;
    vi a(n);
    rep(i,n)cin >> a[i];
    rep(i,n){
        dp[i][0] = i+1;
        dp[i+1][a[i]] += dp[i][0];
        dp[i+1][a[i]] %= MOD;
        loop(j,1,s+1){
            dp[i+1][j] += dp[i][j];
            dp[i+1][j] %= MOD;
            if(j+a[i] <= s)dp[i+1][j+a[i]] += dp[i][j],dp[i+1][j+a[i]] %= MOD;
        }
    }
    //rep(i,n+1)rep(j,s+1)cout << i << " " << j << " " << dp[i][j] << endl;
    //cout << dp[n][s] << endl;
    int ans = 0;
    rep(i,n+1)ans += dp[i][s],ans %= MOD;
    cout << ans << endl;
}


Measured memory_bytes: 70656
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
mod = int(1e+9) + 7
def extgcd(a, b):
  if b == 0:
    return 1, 0
  else:
    x, y, u, v, k, l = 1, 0, 0, 1, a, b
    while l != 0:
      x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
      k, l = l, k % l
    return x
def inved(x):
  a = extgcd(x, mod)
  return a % mod

F = [
  [
    [1, 0, 0, Y[5]-Y[4]+1, 0], 
    [-1, 0, 0, 0, 0]
  ],
  [
    [1, X[5]-X[4]+1, 0, 0, 0], 
    [-1, 0, 0, X[5]-X[4]+1, 0]
  ],
  [
    [1, 0, 0, Y[3]-Y[2]+1, 0], 
    [-1, 0, 0, 0, Y[3]-Y[2]+1]
  ],
  [
    [1, 0, X[3]-X[2]+1, X[3]-X[2]+1, 0], 
    [-1, X[3]-X[2]+1, 0, 0, X[3]-X[2]+1]
  ],
  [
    [1, 0, 0, 0, Y[1]-Y[0]+1], 
    [-1, 0, 0, 0, 0]
  ],
  [
    [1, 0, 0, 0, X[1]-X[0]+1],
    [-1, 0, X[1]-X[0]+1, 0, 0]
  ],
  [
    [1, X[2]-X[5]-1, X[0]-X[3]-1, X[4]+Y[4]-X[3]-Y[3], X[2]+Y[2]-X[1]-Y[1]]
  ]
]
fact = [1 for i in range(2000001)]
invf = [0 for i in range(2000001)]
for i in range(2000000):
  fact[i+1] = ((i+1) * fact[i]) % mod
invf[-1] = inved(fact[2000000])
for i in range(2000000, 0, -1):
  invf[i-1] = (invf[i] * i) % mod
def encryptic(left, mat):
  cont = []
  for i in range(len(left)):
    for j in range(len(mat)):
      tmp = [left[i][0] * mat[j][0]]
      for k in range(1, 5):
        tmp.append(left[i][k] + mat[j][k])
      cont.append(tmp)
  return cont
Poly = [[1, 0, 0, 0, 0]]
for p in F:
  Poly = encryptic(p, Poly)
S = 0
D = {}
for p in Poly:
  a, b, c, d = -p[1], -p[2], p[3], p[4]
  s = p[0]
  M = min(b, c-a-2)
  tmp = 0
  for i in range(M+1):
    pix = (i+1) * invf[2+i+a] * invf[c-i-a-2]
    pix *= invf[b-i] * invf[d+i-b]
    pix %= mod
    tmp += pix
    tmp %= mod
  tmp *= fact[c] * fact[d]
  tmp %= mod
  S += s * tmp
  S %= mod
print(S)

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

using namespace std;

#define INF ((int)2e18)
#define eb emplace_back
#define ii pair<int, int>
#define OK (cerr << "OK" << endl)
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define all(x) x.begin(), x.end()
#define Matrix vector<vector<int>>
#define Mat(n, m, v) vector<vector<int>>(n, vector<int>(m, v))
#define endl '\n'
const int MOD = 1e9 + 7;

signed main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int h, w;

  cin >> h >> w;

  if (h == 1 || w == 1)
    return cout << 1 << endl, 0;

  cout << h * w / 2 + ((h * w) & 1) << endl;
}

Measured memory_bytes: 256
import java.util.*;
// warm-up
// Same pattern multiple times. I think its a sign
public class Main {

	static void solve() {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt(), B = sc.nextInt(), C = sc.nextInt(), X = sc.nextInt(), t=0;
		for (int i=0; i<=A; i++) {
			for (int j=0; j<=B; j++) {
				if ((X-(500*i)-(100*j))%50!=0) continue;
				int k = (X-(500*i)-(100*j))/50;
				if (k>=0 && k<=C) t++;
			}
		}
		System.out.println(t);
		sc.close();		
	}

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

}

Measured memory_bytes: 35728
n, m = map(int,input().split())
dic = {}
ans = 0
for _ in range(m):
    s,c = map(int,input().split())
    if s-1 not in dic.keys():
        dic[s-1] = c
    if s-1 in dic.keys() and dic[s-1] !=c:
        ans = -1
        break
    if s == 1 and c == 0 and n!=1:
        ans = -1
        break
if ans == -1:
    print(ans)
    exit()
if 1 not in dic.keys() and n !=1:
    dic[1] = 0
if 2 not in dic.keys() and n ==3:
    dic[2] = 0  
if 0 not in dic.keys() and n!=1:
    dic[0] = 1
if 0 not in dic.keys() and n==1:
    dic[0] = 0
ls = []
for i in range(n):
    ls.append(str(dic[i]))
ans = ''.join(ls)
print(ans)

Measured memory_bytes: 38384
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
N = 0
A = []


def set_inputs():
    global N, A
    N = get_int()
    A = get_li()
    return


def lcm(a, b):
    return a * b // gcd(a, b)


def main():
    setrecursionlimit(100000)
    set_inputs()
    if N == 1:
        print(A[0] - 1)
        return
    x = reduce(lcm, A) - 1
    print(sum(x % i for i in A))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()


Measured memory_bytes: 5392
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,x,y;
	cin>>x>>y;
	b=y/2-x;
	a=x-b;
	if (a<0||b<0||y%2!=0)
	{
		cout<<"No";
	}
	else   cout<<"Yes";
	return 0;
} 

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
int main(){
	int k,a,b;
	cin>>k>>a>>b;
	if(a%k==0||b%k==0){
		cout<<"OK"<<endl;
	}else{
		int x=b-a;
		int y=a%k;
		if(x+y>=k)cout<<"OK"<<endl;
		else cout<<"NG"<<endl;
	}
} 

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using namespace std;
int main(){
    int n,ans=0;
    cin>>n;
    vector<vector<int>> a(n,vector<int>(n,2));
    rep(i,n){
        int m;
        cin>>m;
        rep(j,m) {
            int o,p;
            cin>>o>>p;
            o--;
            a[i][o]=p;
        }
    }
    for(int i=0;i<(1<<n);i++){
            bool flag=true;
            int p=0;
            vector<int> person(n,2);
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                if(person[j]==0) {
                    flag=false;
                    break;
                }
                person[j]=1;
                p++;
                rep(k,n){
                    if(a[j][k]==1){
                        if(person[k]==0) {
                            flag=false;
                            break;
                        }
                        person[k]=1;
                    }
                    else if(a[j][k]==0){
                        if(person[k]==1) {
                            flag=false;
                            break;
                        }
                        person[k]=0;
                    }
                }
            }
            else{
                if(person[j]==1) {
                    flag=false;
                    break;
                }
                 person[j]=0;
                // rep(k,n){
                //     if(a[j][k]==1){
                //         if(person[k]==1) {
                //             flag=false;
                //             break;
                //         }
                //         person[k]=0;
                //     }
                //     else if(a[j][k]==0){
                //         if(person[k]==0) {
                //             flag=false;
                //             break;
                //         }
                //         person[k]=1;
                //     }
                // }
            }
        }
        if(flag)ans=max(ans,p);
    }
    cout<<ans<<endl;
}



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

const ll MAX = 2500;
ll S[101010];
bool isP[MAX];

void solve() {
    int N;
    cin >> N;
    REP(i, N) cin >> S[i];

    REP2(i, 2, MAX) isP[i] = true;
    vector<ll> P;
    REP2(i, 2, MAX) if (isP[i]) {
        P.push_back(i);
        for (ll j = i + i; j < MAX; j += i) {
            isP[j] = false;
        }
    }

    map<ll, ll> cnt;

    REP(i, N) {
        for (auto p: P) {
            ll p3 = p * p * p;
            while (S[i] % p3 == 0) S[i] /= p3;
        }
        cnt[S[i]] += 1;
    }

    unordered_set<ll> used;
    ll ans = 0;

    for (auto pr : cnt) {
        ll k = pr.first;
        ll v = pr.second;
        if (used.find(k) != used.end()) {
            continue;
        }
        ll counterpart = 1;
        for (auto p : P) {
            if (k % (p * p) == 0) {
                counterpart *= p;
                k /= p * p;
            } else if (k % p == 0) {
                counterpart *= p * p;
                k /= p;
            }
        }
        if (k != 1) {
            counterpart *= k * k;
        }
        used.insert(k);
        used.insert(counterpart);
        if (k == counterpart) {
            ans += 1;
        } else {
            ans += max(v, cnt[counterpart]);
        }
    }

    cout << ans << endl;
}

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


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

using namespace std;

const int P = 1000000000 + 7;

long long qpow(long long a, long long k) {
    long long res = 1;
    while (k) {
        if (k & 1)  res = res * a % P;
        a = a * a % P;
        k >>= 1;
    }
    return res;
}

int main() {
    int n;  cin >> n;
    if (n < 2)  cout << 0 << '\n';
    else {
        long long ans = qpow(10, n) - qpow(9, n) * 2 + qpow(8, n);
        ans = (ans % P + P) % P;
        cout << ans << '\n';
    }
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, 0, n){
        cin >> h[i];
    }
    int state = h[0];
    int ans = 1;
    rep(i, 1, n){
        if(state <= h[i]){
            ans++;
            state = h[i];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;
const int MOD = 1000000007;

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

  int n, query; cin >> n >> query;
  vector<stack<int>> v(1010);

  for (int i = 0; i < query; ++i) {
    int op; cin >> op;
    if (op == 0) {
      int t, x; cin >> t >> x;
      v[t].push(x);
    } else if (op == 1) {
      int t; cin >> t;
      if (v[t].empty()) {
        continue;
      } else {
        cout << v[t].top() << '\n';
      }
    } else {
      int t; cin >> t;
      if (v[t].empty()) {
        continue;
      } else {
        v[t].pop();
      }
    }
  }

  return 0;
}


Measured memory_bytes: 4200
# include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int main(){

  string S; cin >> S;
  string ans = "Good";
  for(int i=0; i < 3; i++){
    if(S[i] == S[i+1]){
      ans = "Bad";
      break;
    }
  }
  cout << ans << endl;

}


Measured memory_bytes: 256
//https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/4/ITP1_4_C
#include <iostream>
#include <string.h>

int main()
{
    using namespace std;

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



Measured memory_bytes: 3096
n = int(input())
s = input()
res=0
for i in range(1000):
    digits=str(i)
    if i<100:
        digits='0'*(3-len(str(i)))+digits
        #print(digits)
    cnt = 0
    for j in s:
        if j==digits[cnt]:
            #print(digits)
            cnt+=1
        if cnt>=3:
            res+=1
            break
print(res)

Measured memory_bytes: 73568
def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    a = b
    return True

  return False

N,K = map(int, input().split())
li = list(map(int, input().split()))

dp = [10**9] * N

for n in range(N):
  if n == 0:
    dp[n] = 0
    continue
  if n == 1:
    dp[n] = abs(li[n] - li[n-1])
    continue

  for k in range(1, K+1):
    if k > n:
      break

    dp[n] = chmin(dp[n], dp[n-k] + abs(li[n] - li[n-k]))

print(dp[-1])

Measured memory_bytes: 52448
#include <stdio.h>

int main()
{
    int n;
    char str[128];
    int i, j, k, l;
    int ans = -1;

    scanf("%d", &n);
    scanf("%s", str);

    for (i = 1; i < n; i++) { // foward = [0,i), back = [i, n)
        int kind[30] = {};
        int temp = 0;

        for (j = 0; j < i; j++) {
            for (k = i; k < n; k++) {
                if (str[j] == str[k] && kind[str[j] - 'a'] == 0) {
                    kind[str[j] - 'a'] = 1;
                    temp++;
                }
            }
        }

        ans = (temp > ans ? temp : ans);
    }

    printf("%d\n", ans);

    return 0;
}


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

int main(){
    int ans = 0;
    int n; cin >> n;
    map<int,int> mp;
    
    rep(i,n){
        int tmp; cin >> tmp;
        mp[tmp]++;
        mp[tmp-1]++;
        mp[tmp+1]++; 
    }

    for(auto a:mp) ans = max(a.second,ans);

    put(ans);
}

Measured memory_bytes: 4736
import sys
import math
import copy
from typing import Tuple, List
input = sys.stdin.readline

class Card:
    def __init__(self, idx):
        self.number = int(idx[1])
        self.design = idx[0]
    def __repr__(self):
        return "{}{}".format (self.design, self.number)


def  print_vec (A: list):
    print (" ".join(map (str, A)))

def swap (A: List, i: int, j: int) -> None:
    temp = A [i]
    A [i] = A [j]
    A [j] = temp



def bubble_sort (C: List [Card]) -> List [Card]:
    for i in range (len (C)):
        for j in range (len (C) - 1, i, -1):
            if C [j].number < C [j-  1].number:
                swap (C, j, j-1)
    return C

def selection_sort (C: List [Card]) -> List [Card]:
    for i in range (len (C)):
        minj = i
        for j in range (i, len (C)):
            if C [j].number < C [minj].number:
                minj = j
        if i != minj:
            swap (C, i, minj)
    return C

if __name__ == "__main__":
    n = int(input())
    vec =  list (map (lambda x: Card (x), input ().split ()))
    bubble_result = bubble_sort (copy.copy (vec))
    print_vec(bubble_result)
    print ("Stable")
    selection_result = selection_sort(copy.copy (vec))
    print_vec (selection_result)
    flag=  True
    for i in range (len (bubble_result)):
        if bubble_result [i] != selection_result [i]:
            flag = False
    if flag:
        print ("Stable")
    else:
        print ("Not stable")



Measured memory_bytes: 7240
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 998244353;

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

  string s;
  cin >> s;

  LL cnt = 0;
  REP(i, s.size() - 1)
  {
    if(s[i]!=s[i+1]){
      cnt++;
    }
  }

  cout << cnt << endl;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

struct UnionFind {
    int n, cc, *u;
    UnionFind() : n(0), cc(0), u(NULL) {}
    UnionFind(int n_) : n(n_), cc(n_) {
	u = new int[n_];
	memset(u, -1, sizeof (int) * n);
    }
    UnionFind(const UnionFind &y) : n(y.n), cc(y.cc) {
	u = new int[y.n];
	memcpy(u, y.u, sizeof (int) * n);
    }
    ~UnionFind() {
	delete[] u; u = NULL;
	n = cc = 0;
    }
    friend void swap(UnionFind &x, UnionFind &y) {
	swap(x.n, y.n); swap(x.cc, y.cc); swap(x.u, y.u);
    }
    UnionFind& operator=(UnionFind y) { 
	swap(*this, y);
	return *this;
    }
    int root(int x) {
	int y = x, t;
	while (u[y] >= 0) y = u[y];
	while (x != y) { t = u[x]; u[x] = y; x = t; }
	return y;
    }
    bool link(int x, int y) {
	x = root(x); y = root(y);
	if (x == y) return false;
	if (u[y] < u[x]) swap(x, y);
	u[x] += u[y]; u[y] = x; cc--;
	return true;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int size(int x) { return -u[root(x)]; }
    int count() { return cc; }
};
int N;
struct Edge {
    int x, y, c;
    bool operator<(const Edge &o) const {
	return c < o.c;
    }
} E[100011];

VI G[100011];
LL dp[100011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N-1) {
	int x, y, c;
	scanf("%d%d%d", &x, &y, &c);
	x--; y--;
	E[i].x = x;
	E[i].y = y;
	E[i].c = c;
    }
    sort(E, E+N-1);
    UnionFind U(N);
    for (int i=N-1; i--;) {
	int x = U.root(E[i].x), y = U.root(E[i].y);
	int sx = U.size(x);
	int sy = U.size(y);
	U.link(x, y);
	int r = U.root(x);
	if (r == x) {
	    G[x].push_back(y);
	    dp[x] += (LL)sy * E[i].c;
	    dp[y] += (LL)sx * E[i].c - dp[x];
	} else {
	    G[y].push_back(x);
	    dp[y] += (LL)sx * E[i].c;
	    dp[x] += (LL)sy * E[i].c - dp[y];
	}
    }

    VI ord;
    ord.reserve(N);
    ord.push_back(U.root(0));
    REP (i, N) {
	int v = ord[i];
	EACH (e, G[v]) {
	    dp[*e] += dp[v];
	    ord.push_back(*e);
	}
    }

    REP (i, N) printf("%lld\n", dp[i]);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 7808
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
//#define uint __int128_t
 
#define pb push_back
#define fi first
#define se second
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define low(a,b) lower_bound(all(a),(b))-(a).begin()
#define upp(a,b) upper_bound(all(a),(b))-(a).begin()
#define fill(i,n) memset(i,n,sizeof(i))
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<vint> vvint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
typedef pair<pint,pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;
 
int N;int a[200010];
unordered_map<int,int> mp;
 
signed main() {
    IOS();
    //(1ll<<N)シフト演算のオーバーフローに気をつける
    cin>>N;
    rep(i,0,N){
        cin>>a[i];
        mp[a[i]]++;
    }
    
    sort(a,a+N);
    reverse(a,a+N);
    int ans=0;
    int x=2;
    rep(i,0,N){
        if(mp[a[i]]==0)continue;
        rrep(j,0,31){
            int x=(1ll<<j);
            if(x<a[i])break;
            if(x-a[i]==a[i]&&mp[a[i]]==1)continue;
            if(mp[x-a[i]]>0){
                ans++;
                mp[x-a[i]]-=1;
                mp[a[i]]-=1;
                break;
            }
        }
    }
    
    cout<<ans<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    return 0;
}

Measured memory_bytes: 30452
import collections

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

k=int(input())
cnt=collections.defaultdict(int)
for i in range(1,k+1):
  for j in range(1,k+1):
    cnt[gcd(i,j)]+=1
ans=0
for i in range(1,k+1):
  for key in cnt.keys():
    ans+=gcd(i,key)*cnt[key]
print(ans)

Measured memory_bytes: 76528
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;
  
#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
  
#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
  
const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
  
  
int main(){
	int i,j,k=0,flag=0;
	int num[28];
	char a,b,c;
	
	string str,rts,xrts;
	cin>>str;
	string strx(str);
	int ix=0;
	/*FOR(i,0,str.length()){
	num[str[i]-'a']++;
	}*/
	while( (ix = strx.find("x", ix)) >= 0 ) {
        strx.erase(ix,1);
    }
	rts=str;
	xrts=strx;
	reverse(rts.begin(), rts.end());
	reverse(xrts.begin(), xrts.end());
	/*for (i = str.length()-1; i>=0; i--) {
    rts[str.length()-1-i]=str[i];
  }*/
	//rts[str.length()]='%0';
	/*for (i = strx.length()-1; i>=0; i--) {
    xrts[strx.length()-1-i]=strx[i];
  }*/
	//xrts[str.length()]='%0';
	//cout<<str<<" "<<rts<<" "<<strx<<" "<<xrts<<endl;
	if(str==rts)cout<<0<<endl;
	else if(strx!=xrts)cout<<-1<<endl;
	else{
		int count=0;
		while(1){
			if(str.length()==1||str.length()==0)break;
			if(str[0]==str[str.length()-1]){
				str.pop_back();
				str.erase(str.begin());
			}else{
				count++;
				if(str[0]=='x'){
				
					str.erase(str.begin());
				}else{
				str.pop_back();
				}
			}
	}
		cout<<count<<endl;
	}
		
	/*FOR(i,0,'z'-'a'){
		if
		if(k==1&&num[i]%2==1){
		
		}
	}*/
	

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
int main() {
    string s;
    cin >> s;
 
    int n = s.size();
    map<string, int> ss;
 
    int cnt[26] = {};
    for (char c : s) {
        cnt[c - 'a']++;
    }
 
    ll ans = 1;
    for (int i = 0; i < n; i++) {
        ans += n - 1 - i - (--cnt[s[i] - 'a']);
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());

            for (int c = 0; c <= 25; c++)
            {
                for (int d = 0; d <= 14; d++)
                {
                    if (4 * c + 7 * d == N)
                    {
                        Console.WriteLine("Yes");
                        return;
                    }
                }
            }
            Console.WriteLine("No");
        }
    }
}

Measured memory_bytes: 13140
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = 998244353
#from decimal import Decimal

n,k=mdata()
A=mdata()
for i in range(k):
    A1=[0]*(n+1)
    for j in range(n):
        A1[max(0,j-A[j])]+=1
        A1[min(n,j+A[j]+1)]-=1
    flag=True
    A[0]=A1[0]
    for j in range(1,n):
        A1[j]+=A1[j-1]
        A[j]=A1[j]
        if A1[j]!=n:
            flag=False
    if flag==True:
        break
print(*A)


Measured memory_bytes: 157232
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<vector<int> > A(M);
	int res = 0;
	for (int i = 0; i < M; i++) {
		int k;
		cin >> k;
		int t;
		for (int j = 0; j < k; j++) {
			cin >> t;
			t--;
			A[i].push_back(t);
		}
	}
	vector<int> P(M);
	for (int i = 0; i < M; i++) {
		cin >> P[i];
	}


	for (int i = 0; i < (1 << N); i++) {
		bool ok = true;
		for (int j = 0; j < M; j++) {
			int cnt = P[j];
			for (int k = 0; k < A[j].size(); k++) {
				cnt ^= ((i >> A[j][k]) & 1);
			}
			if (cnt) {
				ok = false;
				break;
			}
		}
		if (ok)res++;


	}
	cout << res << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

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

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;



int main(void){
  int n;
  cin >> n;
  int t = 0;
  const int T = 86400;
  const int W = 10801;
  VI freq(T, 0);
  REP(i, 0, n) {
    int a, b;
    cin >> a >> b;
    t += a;
    t %= T;
    freq[t]++;
    t += b;
    t %= T;
  }
  VI cumul(2 * T, 0);
  REP(i, 1, 2 * T) {
    cumul[i] = cumul[i - 1] + freq[(i - 1) % T];
  }
  int ma = 0;
  REP(i, 0, 2 * T - W) {
    ma = max(ma, cumul[i + W] - cumul[i]);
  }
  cout << ma << endl;
}


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

int main() {
  
  int a,b,c,p,q;
  cin >> a >> b >> c;
  
  p = b;
  b = a;
  a = p;
  
  q = c;
  c = a;
  a = q;
  
  cout << a <<" " <<  b << " " << c <<endl;
  
  
  
}




Measured memory_bytes: 256
from collections import deque    

n,m=map(int,input().split())
abx=[[0]*(n+2) for i in range(n+2)]
for i in range(m):
    ai,bi,xi=map(int,input().split())
    abx[ai][bi]=max(abx[ai][bi],xi)

pp=[[0]*(n+2) for i in range(n+2)]
for j in range(1,n+2):
    dq=deque()
    for i in range(j,n+2):
        if abx[i][j]>0:
            dq.append([i,abx[i][j]])
    iiii=j-1
    while len(dq):
        ii,xi=dq.popleft()
        if ii+xi>iiii:
            for iii in range(max(ii,iiii+1),ii+xi+1):
                pp[iii][j]=iii-ii+1
                iiii=iii            
icnt=0        
for i in range(1,n+1):
    for j in range(1,i+1):
        abij=pp[i][j-1]-1
        pp[i][j]=max(pp[i][j],abij)
        if pp[i][j]>0:
            icnt+=1

print(icnt)
        
    


Measured memory_bytes: 767344
import sys
readline = sys.stdin.buffer.readline

import heapq
pop,push=heapq.heappop,heapq.heappush

class mincf:
	inf=2*10**18
	
	class E:
		def __init__(self,to,cap,cost,nx):
			self.to=to
			self.cap=cap
			self.cost=cost
			self.nx=nx
			self.rev=None
	
	def __init__(self, n):
		self.n=n
		self.head=[None]*n
		self.h=[0]*n
		self.d=[0]*n
		self.pre=[None]*n
	
	def ae(self,a,b,cap,cost):
		head=self.head
		head[a]=self.E(b,cap,cost,head[a])
		head[b]=self.E(a,0,-cost,head[b])
		head[a].rev=head[b]
		head[b].rev=head[a]
	
	def go(self,s,t,f):
		inf=self.inf
		n=self.n
		head=self.head
		h=self.h
		d=self.d
		pre=self.pre
		pq=[(0,s)]
		
		d[0]=0
		d[1:]=[inf]*(n-1)
		while pq:
			(a,v)=pop(pq)
			if d[v]<a:
				continue
			if v==t:
				break
			
			e=head[v]
			while e is not None:
				if e.cap>0:
					w=d[v]+e.cost+h[v]-h[e.to]
					if w<d[e.to]:
						d[e.to]=w
						push(pq,(w,e.to))
						pre[e.to]=e
				e=e.nx
		
		if d[t]==inf:
			return (0,0)
		
		for i in range(n):
			h[i]=min(h[i]+min(d[i],d[t]),inf)
		
		a=f
		v=t
		while v!=s:
			a=min(a,pre[v].cap)
			v=pre[v].rev.to
		v=t
		while v!=s:
			x=pre[v]
			y=x.rev
			x.cap-=a
			y.cap+=a
			v=y.to
		
		return (a,h[t])
	
	def calc(self,s,t,f=None):
		if f is None:
			f=self.inf
		amount=0
		cost=0
		while f>0:
			a,c=self.go(s,t,f)
			if a==0:
				break
			amount+=a
			f-=a
			cost+=a*c
		return (amount,cost)

n,m=map(int,readline().split())
w=[readline().decode('utf-8') for _ in range(n)]
idx=[[-1]*m for _ in range(n)]

s=0
ps=[]

for i in range(n):
	for j in range(m):
		if w[i][j]=='o':
			ps.append((i,j))
		if w[i][j]!='#':
			idx[i][j]=s
			s+=1

ans=0
mcf=mincf(1+s+1)

for i,j in ps:
	ans+=n-i+m-j
	mcf.ae(0,1+idx[i][j],1,0)

for i in range(n):
	for j in range(m):
		if idx[i][j]!=-1:
			mcf.ae(1+idx[i][j],1+s,1,n-i+m-j)
			if i+1<n and idx[i+1][j]!=-1:
				mcf.ae(1+idx[i][j],1+idx[i+1][j],mcf.inf,0)
			if j+1<m and idx[i][j+1]!=-1:
				mcf.ae(1+idx[i][j],1+idx[i][j+1],mcf.inf,0)

f,cost=mcf.calc(0,1+s)
assert f==len(ps)
print(ans-cost)


Measured memory_bytes: 71664
#include<stdio.h>
#include<stdlib.h>

void push(int);
int pop(void);
int count=0;
int Stack[100];

int main(void){
  int i,j;
  char s[100];

  while( scanf("%s",s) != EOF ){
    if ( s[0] == '+' ){
      i=pop();
      j=pop();
      push(i+j);

    } else if ( s[0] == '-' ){
      i=pop();
      j=pop();
      push(j-i);

    } else if ( s[0] == '*' ){
      i=pop();
      j=pop();
      push(i*j);

    } else {
      i = atoi(s);
      push(i);
    }
  }

  printf("%d\n",Stack[0]);
  return 0;
}

void push(int x){
  Stack[count]=x;
  count++;
}
int pop(void){
  if(count==0){
    printf("underflow\n");
    return 0;
  }
  else count--;
  return Stack[count];
}

Measured memory_bytes: 0
import sys
n = int (sys.stdin.readline())
a = map(int, sys.stdin.readline().split())

cur1 = a[0]
cur2 = sum(a) - cur1
res = 10 ** 15
for i in a[1:]:
  res = min (res, abs (cur1 - cur2))
  cur1 += i
  cur2 -= i
print res

Measured memory_bytes: 18440
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

main() {
    int N,C,K; cin >> N >> C >> K;
    int T[N]; rep(i,N) cin >> T[i];
    sort(T,T+N);
    int time=0; int cnt=0; int ans=0;
    rep(i,N){
        cnt++;
        if(!i) {time=T[i]; ans++;}
        else if(cnt>C){
            ans++; time=T[i]; cnt=1;
        }
        else if(time+K<T[i]){
            ans++; time=T[i]; cnt=1;
        } 
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
n,d = map(int,input().split())
xy = []
for i in range(n):
    XY = list(map(int,input().split()))
    xy.append(XY)
z = 0
for i in range(n):
    if xy[i][0] * xy[i][0] + xy[i][1] * xy[i][1] <= d * d:
        z += 1
print(z)

Measured memory_bytes: 45400
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll A, B, C; cin >> A >> B >> C;
  if(A%2 == 1 || B%2 == 1 || C%2 == 1){
    cout << 0 << endl;
    return 0;
  }
  if(A == B && B == C){
    cout << -1 << endl;
    return 0;
  }
  ll ans = 0;
  while(A%2 == 0 && B%2 == 0 && C%2 == 0){
    ll a = A/2, b = B/2, c = C/2;
    A = b + c;
    B = a + c;
    C = a + b;
    ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



def bi_search(k):
    ok = 0
    ng = n // k + 1
    while ng > ok + 1:
        mid = (ng + ok) // 2
        if calc(mid, k):
            ok = mid
        else:
            ng = mid
    return ok


def calc(x, k):
    # x回できるか?
    l = bisect_left(L, (x, 0))
    # 全部使えるのが左側、l回しか使えないのが右側。
    if kv_acc[l - 1] + acc[l] * x >= k * x:
        return True
    else:
        return False




n = I()
A = LI()
L = [(0, 0)] + sorted([(k, v) for k, v in Counter(Counter(A).values()).items()])
m = len(L)
acc = [0] * (m + 1)
for i in range(m - 1, -1, -1):
    acc[i] = acc[i + 1] + L[i][1]

kv_acc = list(accumulate([k * v for k, v in L]))
for k in range(1, n + 1):
    print(bi_search(k))




Measured memory_bytes: 118952