akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define int long long
const int INF = 1e18;

const int MAX_H = 55;
const int MAX_W = 55;
char c[MAX_H][MAX_W];
int d[MAX_H][MAX_W],h,w;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool contain(int x,int y){
    return (0<=x&&x<MAX_H&&0<=y&&y<MAX_W);
}
bool cell(int x,int y){
    return (c[x][y]=='.');//右辺もいじろう
}

void BFS(int sx,int sy){
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            d[i][j] = INF;
        }
    }
    d[sx][sy]=0;
    queue<P> q;
    q.push({sx,sy});
    int nx,ny;
    while(!q.empty()){
        P p = q.front();q.pop();
        int x = p.first,y = p.second;
        if(x==h-1&&y==w-1){break;}
        for(int i=0;i<4;i++){
            nx = x + dx[i];
            ny = y + dy[i];
            if(!contain(nx,ny)||!cell(nx,ny)||d[nx][ny]!=INF){continue;}
            d[nx][ny] = d[x][y] + 1;
            q.push({nx,ny});
        } 
    }
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>h>>w;
    int white = 0;
    rep(i,0,h){
        rep(j,0,w){
            cin>>c[i][j];
            if(c[i][j]=='.'){white++;}
        }
    }
    BFS(0,0);
    if(d[h-1][w-1]!=INF)cout<<white-d[h-1][w-1]-1<<endl;
    else{cout<<-1<<endl;}
}

Measured memory_bytes: 256
#include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    using namespace std;
     
    typedef double r32;
     
    int n, d, x;
     
    int main()
    {
    	cin >> n >> d >> x;
     
    	r32 l = (d + d + (n * 2.0 - 1.0) * x) * n;
    	r32 v = 0;
    	for (int i = 1; i <= n; ++i)
    		v = (1.0 - 1.0 / i / i) * v + 0.5 / i;
     
    	printf("%.16f\n", v * l);
     
    	return 0;
    }

Measured memory_bytes: 256
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

bool b[60000];

int main()
{
	memset(b,1,sizeof(b));
	b[0] = b[1] = false;
	for (int i = 2; i < 300; i++)
		if(b[i]) for(int j = i * 2; j < 60000; j += i) b[j] = false;

	int n;
	while(cin>>n){
		int a,c;
		for (int i = n - 1; i >= 0 ; i--) if(b[i]){ a = i; break;}
		for (int i = n + 1; i < 60000; i++) if(b[i]){ c = i; break; }
		printf("%d %d\n",a,c);
	}
	return 0;
}

Measured memory_bytes: 0
#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<string>
using namespace std;
map<string,int>mp;
char s[15];
int main()
{
	int n;
	scanf("%d\n",&n);
	string tmp;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		//scanf("\n");
		string tmp="";
		int ls=strlen(s);
		for(int i=0;i<ls;i++)
		{
			tmp+=s[i];
		}
		if(mp[tmp]==0)
		{
			mp[tmp]=1;
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
} 

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

int main(){
    ll N;
    cin >> N;
    map<ll,ll> mp;
    rep(i, 0, N){
        ll a;
        cin >> a;
        mp[a]++;
        mp[a-1]++;
        mp[a+1]++;
    }
    ll ans = 0;
    for(auto p : mp) ans = max(ans, p.second);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6144
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a_cs = [0] * (n + 1)
b_cs = [0] * (m + 1)

for i in range(n):
    a_cs[i + 1] = a_cs[i] + a[i]
for i in range(m):
    b_cs[i + 1] = b_cs[i] + b[i]

ans = 0
j = m
for i in range(n + 1):
    while j > 0 and a_cs[i] + b_cs[j] > k:
        j -= 1

    if a_cs[i] + b_cs[j] <= k:
        ans = max(ans, i + j)

print(ans)


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

 
int main() {
  int n;
  cin>>n;
  
  vector<int> h(n);
  int cnt=0;
  int cnt_max=0;

  for(int i=0;i<n;i++){
    cin>>h.at(i);
  }
  
  for(int i=1;i<n;i++){
    if(h.at(i-1)>=h.at(i))
      cnt++;
    else
      cnt=0; 
    cnt_max=max(cnt,cnt_max);
  }
  
  cout<<cnt_max<<endl;
  
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
static const int INFTY = (1 << 21);
ll func(ll a, ll b){
    ll x = 0, y = 0;
    while(a > 0){
        a /= 10;
        x++;
    }
    while(b > 0){
        b /= 10;
        y++;
    }
    return max(x, y);
}
int main(){
    ll N;
    cin >> N;
    ll ans = INFTY;
    for(ll i = 1; i * i <= N; i++){
        if(N % i == 0){
            ans = min(ans, func(i, N / i));
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
import itertools
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


def solve():
    # 消していいやつ
    useless = [[0] * N for _ in range(N)]

    # 1 つ経由するのだけ考えれば OK
    for st, en in itertools.combinations(range(N), r=2):
        for via in range(N):
            if via in [st, en]:
                continue
            if A[st][via] + A[via][en] < A[st][en]:
                return -1
            if A[st][via] + A[via][en] == A[st][en]:
                useless[st][en] = True
                useless[en][st] = True
    return sum([A[s][e] for s, e in itertools.product(range(N), repeat=2) if not useless[s][e]]) // 2


print(solve())


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

const int mod = 1000000007;
int sub(long l, long r, int k) {
  --r;
  long dp[2][2][64] = {};
  dp[1][1][k] = 1;
  for (int i = k - 1; i >= 0; --i) {
    for (int p : { 0, 1 }) {
      for (int q : { 0, 1 }) {
        for (int d : { 0, 1, 2 }) {
          int a = d >= 2;
          int b = d >= 1;
          int x = ((l >> i) & 1) - a;
          int y = b - ((r >> i) & 1);
          if (p == 1 && x == 1) continue;
          if (q == 1 && y == 1) continue;
          int np = p == 1 && x == 0;
          int nq = q == 1 && y == 0;
          dp[np][nq][i] += dp[p][q][i + 1];
          dp[np][nq][i] %= mod;
        }
      }
    }
  }
  
  long sum = 0;
  for (int p : { 0, 1 }) {
    for (int q : { 0, 1 }) {
      sum += dp[p][q][0];
      sum %= mod;
    }
  }
  return sum;
}

int main() {
  long l, r;
  cin >> l >> r;
  ++r;
  long sum = 0;
  for (int z = 0; z < 62; ++z) {
    long p = max(l, 1l << z);
    long q = min(r, 2l << z);
    if (p >= q) continue;
    sum = (sum + sub(p, q, z + 1)) % mod;
  }
  cout << sum << endl;
}


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

int main() {
  //入力値取得
  int H, W;	cin >> H >> W;
  string S[H];
  for(int i=0; i<H; i++)
  	cin >> S[i];
  
  //取得確認
  //cout << H << W << endl;
  //for(int i=0; i<H; i++)
  //	cout << S[i] << endl;
  
  //爆弾位置取得
  for(int y=0; y<H; y++){
    for(int x=0; x<W; x++){
      //cout << S[y].at(x);
      if(S[y].at(x) == '#'){
        cout << S[y].at(x);
        //continue;
      }
      else {
        int counter = 0;
        for(int i=-1; i<=1; i++){
          for(int j=-1; j<=1; j++){
            if(i==0 && j==0)
              continue;
          
            
            if((y+i)>=0 && (y+i)<=(H-1)
              	&& (x+j)>=0 && (x+j)<=(W-1))            
              if(S[y+i].at(x+j) == '#')
                counter++;
          }
        }
        cout << counter;
      }
    }
    cout << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
const ll mod=1e9+7;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

map<ll,vector<ll>>graph;
vector<ll>deg(100005,0);
vector<ll>dp(100005,0);
queue<ll>q;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        deg[b]++;
    }
    for(ll i=1;i<=n;i++){
        if(deg[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        ll tete=q.front();
        q.pop();
        vector<ll>::iterator it=graph[tete].begin();
        for(it;it!=graph[tete].end();it++){
            dp[*it]=max(dp[*it],dp[tete]+1);
            deg[*it]--;
            if(deg[*it]==0)q.push(*it);
        }
    }
    ll res=0;
    for(ll i=1;i<=n;i++){
        res=max(res,dp[i]);
    }
    cout<<res<<endl;
    return 0;
    }


Measured memory_bytes: 12800
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	int N, num = 0;
	std::cin >> N;

	std::vector<int> L(2*N);

	for(int i = 0; i < 2*N; i++) {
		std::cin >> L[i];
	}

	std::sort(L.begin(), L.end());

	for (int i = 0; i < (2 * N); i++) {
		if (!(i & 1)) {
			num += L[i];
		}
	}

	std::cout << num << std::endl;

	return 0;
}


Measured memory_bytes: 256
S = input()
if S == "SUN":
  print(7)
elif S == "MON":
  print(6)
elif S == "TUE":
  print(5)
elif S == "WED":
  print(4)
elif S == "THU":
  print(3)
elif S == "FRI":
  print(2)
elif S == "SAT":
  print(1)

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

using namespace std;

int main() {
    int a, b;
    string s;
    cin >> a >> b >> s;
    for (int i = 0; i < a+b+1; i++) {
        if (i == a && s[i] != '-') {
            cout << "No" << endl;
            return 0;
        }
        if (i != a && s[i] == '-') {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#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++)
using namespace std;
using P = pair<int, int>; 
using ll = long long;

int main()
{

  ll n;
  cin >> n;
  cout << (n / 500 * 1000) + ((n % 500) / 5 * 5) << endl;
  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


int main() {

	string S;
	cin >> S;
	
	for(int i = 0; i < S.size(); i++){
		if((i + 1) % 2 == 0){
			if(S[i] == 'R'){
				cout << "No" << endl;
				return 0;
			}
			
		}else{
			if(S[i] == 'L'){
				cout << "No" << endl;
				return 0;
			}	
			
		}
			
		
	}
	
	cout << "Yes" << endl;

    return 0;
}


/*

for(int i = 0; i < N; i++){
	
}

for(int i = 0; i < N; i++){
	for(int j = 0; j < N; j++){
		
	}
}


*/


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define pii pair<int, int>
#define pll pair<long long, long long>
const double PI = acos(-1);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////////////////////

struct RollingHash {
    typedef unsigned long long ull;

    const ull MASK30 = (1ull << 30) - 1;
    const ull MASK31 = (1ull << 31) - 1;
    const ull mod = (1ull << 61) - 1;
    const ull POSITIVIZER = mod * 3;
    const ull base = 10007;

    vector<ull> hash,power;

    RollingHash(const string &s) {
        int sz = s.size();
        hash.assign(sz + 1,0);
        power.assign(sz + 1,1);
        for (int i = 0; i < sz; i++) {
            power[i+1] = CalcMod(Mul(power[i],base));
            hash[i+1] = CalcMod(Mul(hash[i],base) + s[i]);
        }
    }

    ull get(int l, int r) {
        ull res;
        res = CalcMod(hash[r] + POSITIVIZER - Mul(hash[l],power[r-l]));
        return res;
    }


    ull Mul (ull a, ull b) {
        ull au = a >> 31;
        ull ad = a & MASK31;
        ull bu = b >> 31;
        ull bd = b & MASK31;
        ull mid = ad * bu + au * bd;
        ull midu = mid >> 30;
        ull midd = mid & MASK30;
        return (au * bu * 2 + midu + (midd << 31) + ad * bd);
    }

    ull CalcMod(ull val) {
        val = (val & mod) + (val >> 61);
        if (val > mod) val -= mod;
        return val;
    }
};

int N;
string S;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> S;

    RollingHash RH(S);
    int left = 0;
    int right = N;
    while (right - left > 1) {
        int mid = (left+right)/2;
        set<unsigned long long> dic;
        bool ok = false;
        for (int i = 0; i <= N-2*mid; i++) {
            dic.emplace(RH.get(i,i+mid));
            if (dic.count(RH.get(i+mid,i+2*mid))) ok = true;
        }
        if (ok) left = mid;
        else right = mid;
    }

    cout << left << endl;
}


Measured memory_bytes: 640
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (int i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter cout << endl
#define siz(x) ((int)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef queue <int> qi ;
typedef queue <pii> qii ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int maxn = 1e6 + 10 ;
const int inf = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 1e9 + 7 ;
const double eps = 1e-7 ;
template <class T> void read(T &a)
{
	int f = 1 ; a = 0;
	char ch = getchar() ;
	while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
	while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
	a *= f;
}

ll n, ans;

ll a[maxn], b[maxn];

priority_queue <pair<ll, ll> > q;

signed main()
{
	scanf("%lld", &n);
	rep(i, 1, n) scanf("%lld", &a[i]);
	rep(i, 1, n) scanf("%lld", &b[i]);
	auto c = [](ll a) -> ll
	{
		return (a + n - 1ll) % n + 1ll;
	};
	rep(i, 1, n) if(b[c(i - 1)] + b[c(i + 1)] <= b[i] - a[i]) q.push(mp(b[c(i - 1)] + b[c(i + 1)], i));
	while(!q.empty())
	{
		ll now = q.top().se, val = q.top().fi;
		// cout << now << ' ' << val << endl;
		q.pop();
		ans += (b[now] - a[now]) / (val);
		b[now] = (b[now] - a[now]) % val + a[now];
		if(b[c(now - 2)] + b[now] <= b[c(now - 1)] - a[c(now - 1)]) q.push(mp(b[c(now - 2)] + b[now], c(now - 1)));
		if(b[c(now + 2)] + b[now] <= b[c(now + 1)] - a[c(now + 1)]) q.push(mp(b[c(now + 2)] + b[now], c(now + 1)));
	}
	rep(i, 1, n) if(b[i] != a[i]) return puts("-1"), 0;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 8052
#include <stdio.h>
int main(void)
{
    int a,b,c,d;
    scanf("%d%d%d",&a,&b,&c);
    if(a>b)
    {
        d=a;
        a=b;
        b=d;
    }
    if(b>c)
    {
        d=b;
        b=c;
        c=d;
    }
    if(a>b)
    {
        d=a;
        a=b;
        b=d;
    }
    printf("%d %d %d\n",a,b,c);
    return 0;
}


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

int power6(int n){
  int pn = 1;
  for(int i = 0; i < n; i++){
  	pn *= 6;
  }
  return pn;
}

int log6(int n){
  int ln = 0;
  while(n / 6 != 0){
    ln++;
    n /= 6;
  }
  return ln;
}

int power9(int n){
  int pn = 1;
  for(int i = 0; i < n; i++){
    pn *= 9;
  }
  return pn;
}

int log9(int n){
  int ln = 0;
  while(n / 9 != 0){
    ln++;
    n /= 9;
  }
  return ln;
}

int memo[100001]{0};

int rec(int n){
  if(n < 6){
    return n;
  }
  if(memo[n] != 0){
    return memo[n];
  }
  return memo[n] = min(rec(n - power9(log9(n))) + 1, rec(n - power6(log6(n))) + 1);
}

int main()
{
  int n;
  cin >> n;
  cout << rec(n) << endl;
}

Measured memory_bytes: 384
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

#[allow(dead_code)]
struct Scanner<'a> {
    cin: StdinLock<'a>,
}
#[allow(dead_code)]
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn input<T: FromStr>(&mut self) -> T {
        self.read().unwrap()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let s: String = sc.input();
    let cs: Vec<char> = s.chars().collect();


    let ans = if cs[0] == *cs.last().unwrap() {
        if cs.len() % 2 == 0 {
            "First"
        } else {
            "Second"
        }
    } else {
        if cs.len() % 2 == 0 {
            "Second"
        } else {
            "First"
        }
    };

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<class Z> Z gcd(Z a, Z b) {
  while (b) swap(a %= b, b);
  return a;
}
template<class Z> Z lcm(Z a, Z b) { return a / gcd(a, b) * b; }

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  constexpr int n = 500;
  VV<lint> a(n, V<lint>(n));
  set<lint> se;
  lint x = 10;
  for (int k = 1; k < 2 * n - 1; k += 4) {
    for (int i = 0; i < n; ++i) {
      int j = k - i;
      if (j < 0 or j >= n) continue;
      if (~i & 1) {
        a[i][j] = x;
        se.insert(x);
      } else {
        a[i][j] = 2 * x;
        se.insert(2 * x);
        while (se.count(x)) ++x;
      }
    }
  }
  for (int k = 2 * n - 5; k >= 0; k -= 4) {
    for (int i = 0; i < n; ++i) {
      int j = k - i;
      if (j < 0 or j >= n) continue;
      if (~i & 1) {
        a[i][j] = x;
        se.insert(x);
      } else {
        a[i][j] = 2 * x;
        se.insert(2 * x);
        while (se.count(x)) ++x;
      }
    }
  }
  V<> di{1, -1, 0, 0};
  V<> dj{0, 0, 1, -1};
  for (int k = 0; k < 2 * n - 1; k += 2) {
    for (int i = 0; i < n; ++i) {
      int j = k - i;
      if (j < 0 or j >= n) continue;
      x = 1;
      for (int d = 0; d < 4; ++d) {
        int ni = i + di[d];
        int nj = j + dj[d];
        if (ni < 0 or ni >= n) continue;
        if (nj < 0 or nj >= n) continue;
        x = lcm(x, a[ni][nj]);
      }
      // while (x < 1e5) x *= 2;
      while (se.count(x + 1)) x *= 2;
      a[i][j] = x + 1;
      se.insert(x + 1);
    }
  }

  set<lint> s;
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
    assert(a[i][j] <= 1e15);
    if (a[i][j] > 1e15) {
      cerr << i << ' ' << j << '\n';
      cerr << a[i][j] << '\n';
      for (int d = 0; d < 4; ++d) {
        int ni = i + di[d];
        int nj = j + dj[d];
        if (ni < 0 or ni >= n) continue;
        if (nj < 0 or nj >= n) continue;
        cerr << a[ni][nj] << '\n';
      }
      return 0;
    }
    if (s.count(a[i][j])) {
      cerr << i << ' ' << j << '\n';
      cerr << a[i][j] << '\n';
    }
    s.insert(a[i][j]);
  }
  assert(s.size() == n * n);

  int N; cin >> N;
  for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
    cout << a[i][j] << " \n"[j == N - 1];
  }
}

Measured memory_bytes: 28288
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;



int main() {
  int A, B, C; cin >> A >> B >> C;
  string result = "NO";
  rep(i, B) if ((A*i)%B==C) result = "YES";
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size)
#define MOD 1000000007
const long long mod = 1e9+7;
typedef vector<long long> Vl;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef long long ll;

int main(){
    int a,b;
    cin >> a >> b; 
    cout << (a-1)*(b-1) << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

a_list.sort()
b_list.sort()
c_list.sort()
n_b = []
current = 0
for i in range(n):
    a = a_list[i]
    while current <= n-1 and b_list[current] <= a:
        current += 1
    n_b.append(n-current)
n_c = []
current = 0
for i in range(n):
    b = b_list[i]
    while current <= n-1 and c_list[current] <= b:
        current += 1
    n_c.append(n-current)
cum_nc = [0]*n
cum_nc[0] = n_c[n-1]
for i in range(1, n):
    cum_nc[i] = cum_nc[i-1] + n_c[n-1-i]
ans = 0

for i in n_b:
    if i > 0:
        ans += cum_nc[i-1]
print(ans)


Measured memory_bytes: 28384
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
#define INF INT_MAX/2

string DIR = "LRUD";
double dx[4] = { -1,1,0,0 };
double dy[4] = {0,0,1,-1};
int main() {
	int N;
	cin >> N;
	vector<vector<double>>X(4);
	vector<vector<double>>Y(4);
	rep(i, 0, N) {
		double x, y;
		char c;
		cin >> x >> y >> c;
		int d = DIR.find(c);
		X[d].pb(x);
		Y[d].pb(y);
	}

	vector<double>xs;
	vector<double>ys;
	rep(i, 0, 4) {
		if (X[i].size()) {
			xs.pb(*max_element(all(X[i])));
			xs.pb(*min_element(all(X[i])));
		}
		if (Y[i].size()) {
			ys.pb(*max_element(all(Y[i])));
			ys.pb(*min_element(all(Y[i])));
		}
	}

	vector<double>cand;
	rep(i, 0, xs.size())rep(j, 0, xs.size()) {
		cand.pb(abs(xs[i] - xs[j]));
		cand.pb(abs(xs[i]-xs[j])/2);
	}
	rep(i, 0, ys.size())rep(j, 0, ys.size()) {
		cand.pb(abs(ys[i] - ys[j]));
		cand.pb(abs(ys[i] - ys[j]) / 2);
	}

	double ans = inf;
	fore(time, cand) {
		double xma = -inf, xmi = inf, yma = -inf, ymi = inf;
		rep(i, 0, 4) {
			fore(x, X[i]) {
				double xaf = x + dx[i] * time;
				xma = max(xma,xaf);
				xmi = min(xmi, xaf);
			}
			fore(y, Y[i]) {
				double yaf = y + dy[i] * time;
				yma = max(yma, yaf);
				ymi = min(ymi, yaf);
			}
		}
		ans = min(ans, (xma - xmi)*(yma - ymi));
	}
	cout << setprecision(12) << ans << endl;

	return 0;
}


Measured memory_bytes: 2256
#include <bits/stdc++.h>
#define MOD (ll)(1e9 + 7)
#define MAX (ll)(200 + 4)
#define INF (ll)(1e17)
using namespace std;
using ll =  long long;
using ld = long double;

int val[MAX];
queue<int> q;
vector<int> gr[MAX];
bool vis[MAX];

bool dfs (int node) {
	int a = 1;
	for (int x : gr[node]) {
		if (val[x]) {
			if (val[x] == val[node]) {
				return 0;
			}
			continue;
		}
		val[x] = !(val[node] - 1) + 1;
		a &= dfs (x);
	}
	return a;
}

int bfs () {
	int cc = 0;
	while (q.size ()) {
		int ss = q.size ();
		cc++;
		for (int i = 0; i < ss; i++) {
			int node = q.front ();
			q.pop ();
			for (int x : gr[node]) {
				if (!vis[x]) {
					vis[x] = 1;
					q.push (x);
				}
			}
		}
	}
	return cc;
}

int main () {
	int n;
	char ch;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> ch;
			if (ch == '1') {
				gr[i + 1].push_back (j + 1);
			}
		}
	}
	val[1] = 1;
	if (dfs (1) == 0) {
		cout << "-1\n";
		return 0;
	}
	int ma = 0;
	for (int i = 1; i <= n; i++) {
		q.push (i);
		vis[i] = 1;
		ma = max (ma, bfs ());
		fill (vis, vis + MAX, 0);
	}
	cout << ma << "\n";
}


Measured memory_bytes: 512
p = 1000000007

n, m = map(int, input().split())

u = [0]*(n+1)
F = [0]*(n+1)
for i in range(m):
	x = int(input())
	u[x] = 1

F[0] = 1
for i in range(1, n+1):
	F[i] = (F[i-1]+F[i-2])%p
	if u[i] == 1: F[i] = 0

print(F[n])


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

int main() {
  string n;
  cin >> n;
  for(int i = 0; i < 3; i++) {
    if (n[i] == '1') n[i] = '9';
    else n[i] = '1';
  }
  cout << n << endl;
}

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

vector<int> v;

int main(){
	int n;
	cin >> n;
	string s = to_string(n);
	int ss = 0;
	for(int i = 0; i < (int)s.size(); i++){
		ss += s[i] - '0';
	}

	if(n % ss == 0) cout << "Yes" << endl;
	else cout << "No" << endl;


	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int a, b, h;
	if (scanf("%d", &a) != 1) return 1;
	if (scanf("%d", &b) != 1) return 1;
	if (scanf("%d", &h) != 1) return 1;
	printf("%d\n", (a + b) * h / 2);
	return 0;
}


Measured memory_bytes: 128
N, K = [int(s) for s in input().split()]
rans = []
for _ in range(K):
    l, r= [int(s) for s in input().split()]
    rans.append((l, r))
rans.sort()

prev = -1
newrans = []
for ran in rans:
    l, r = ran
    if l <= prev:
        newrans[-1] = max(r, newrans[-1])
    else:
        newrans.append([l,r])
    prev = max(prev, r)

MOD = 998244353

rans = newrans
sums = [0, 1]
s = 1
# print(rans)
for i in range(2, N+1):
    # print(sums, i)
    for ran in rans:
        l = i - ran[0]
        r = max(i - ran[1] - 1, 0)
        # print(l, r, s)
        if l >= 0:
            s = (s + sums[l] - sums[r]) % 998244353
    sums.append(s)
# print(sums)
if N == 1:
    print(1)
else:
    print((sums[-1] - sums[-2]) % 998244353)


Measured memory_bytes: 80000
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

    string S; cin >> S;
    int N=SZ(S);
    int cnt=0;
    rep(i,SZ(S)/2){
        if(S[i]!=S[N-i-1]) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
from collections import deque

N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    links[a].append((b, c))
    links[b].append((a, c))

Q, K = map(int, input().split())

d = [float('inf')] * (N + 1)
d[K] = 0
q = deque([K])
while q:
    i = q.popleft()
    di = d[i]
    for j, c in links[i]:
        if di + c < d[j]:
            d[j] = di + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))


Measured memory_bytes: 55604
/* 
 * Author: aps
 * Time: 18-06-2019 17:33:23
**/
#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long int ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef pair<int,int> pii;

const ll inf = 1e18;
const ll mod = 1e9+7;

inline ll add(ll x, ll y) { x += y; if (x >= mod) x -= mod; return x;}
inline ll sub(ll x, ll y) { x -= y; if (x < 0) x += mod; return x;}
inline ll mul(ll x, ll y) { return ((x % mod) * (y % mod)) % mod;}
inline ll power(ll a, ll b) {
    ll x = 1;
    while (b) {
        if (b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}
inline ll inv(ll a) { return power(a, mod - 2);}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    ll w,h,x,y; cin >> w >> h >> x >> y;

    long double ans = (long double)(1.0*w*h)/2.0;
    int ways = 0;
    if(x*2 == w && y*2 == h){
        ways = 1;
    }

    cout << fixed << setprecision(9) << ans << " " << ways << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define fi first
#define se second
#define pb push_back
#define forn(i,n) for(int i=0;i<(n);i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forr(i,n) for(int i=n;i>=0;i--)
#define all(x) x.begin(), x.end()
const int MAXN = 2e5 +5;

void fio(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}

LL dp[MAXN], odds[MAXN];

int main(){
  fio();
  int n; cin>>n;
  vector<LL> v(n);
  forn(i,n) cin>>v[i];
  forn(i,n) odds[i] = ( i%2 || i<2 ?0:odds[i-2]) + v[i];
  for(int i=1;i<n;i++)
  	dp[i] = max((i>=2?dp[i-2]:0)+v[i], i%2?odds[i-1]:dp[i-1]);
  cout<<dp[n-1]<<endl;
  return 0;
}

Measured memory_bytes: 7928
#include<iostream>
#include<string>
#include<atcoder/dsu>
#include<algorithm>
#include<vector>
using namespace std;
using namespace atcoder;
using ll=long long;
int main(){

  int N,M;
  cin>>N>>M;
  dsu d(N);
  vector<bool>key(N);
  int a,b;
  for(int i=1;i<=M;i++){
    cin>>a>>b;
    d.merge(a-1,b-1);
  }
  for(int i=0;i<=N-1;i++){
  
    key[d.leader(i)]=1;
  }
  int ans=0;
  for(int i=0;i<=N-1;i++){
  
    ans+=key[i];
  }
  cout<<ans-1;
  return 0;
}

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

int main(){
  int n,k;cin>>n>>k;
  vector<bool> trick(n,true);
  
  for(int i=0;i<k;i++){
    int d;cin>>d;
    for(int j=0;j<d;j++){
      int x;cin>>x;x--;
      if(trick[x])trick[x]=false;
    }
  }
  int ans=0;
  for(int x:trick)if(x)ans++;
  cout<<ans<<endl;
}

Measured memory_bytes: 3628
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            Scanner sc = new Scanner();
            int N = sc.nextInt();
            int W = sc.nextInt();

            int[] bangou = new int[N + 1];
            for (int i = 0; i < N + 1; i++)
            {
                bangou[i] = i;
            }            


            for (int i = 0; i < W; i++)
            {
            	string line = Console.ReadLine();
                string[] str = line.Split(',');
                int a = int.Parse(str[0]);
                int b = int.Parse(str[1]);
				

                int temp = bangou[a];
                bangou[a] = bangou[b];
                bangou[b] = temp;
            }

            for (int i = 1; i < N + 1; i++)
            {
                Console.WriteLine(bangou[i]);
            }


        }
    }
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        do
        {
            s = Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries);
        } while ((s.Length == 1 && s[0] == "") || s.Length == 0);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

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

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

  int x = a + b, y = c + d;

  if(x == y) cout << "Balanced";
  else if(x < y) cout << "Right";
  else cout << "Left";

  cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e18;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int mod_pow(int x,int y) {
    int res = 1;
    while(y > 0) {
        if(y%2) {
            res = res*x%mod;
        }
        x = x*x%mod;
        y/=2;
    }
    return res;
}
int cnt[1000005];
signed main() {
    int N;
    cin >> N;
    vector<int>A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        int X = A[i];
        for(int j = 2; j*j <= A[i]; j++) {
            int res = 0;
            while (X%j == 0) {
                res++;
                X/=j;
            }
            cnt[j] = max(cnt[j],res);
        }
        if(X) {
            cnt[X] = max(cnt[X],1LL);
        }
    }
    int res = 1;
    for(int i = 1; i <= 1000000; i++) {
        res *= mod_pow(i,cnt[i]);
        res %= mod;
    }
    int ans = 0;
    for(int i = 0; i < N; i++) {
        ans += res*mod_pow(A[i],mod-2);
        ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 7264
#include <iostream>
#include <cmath>
using namespace std;
bool flag[10000001];

int main(){
    int n=0,ans=0,co=0;
	for(int i=0;i <= 1000000;i++){
		if(i<=1)flag[i]=false;
		else flag[i]=true;
	}
	for(int i=2;i <= 1001 ;i++){
		if(flag[i]==true){
			for(int j=i*2 ; j<=1000000 ; j=j+i){
				flag[j] = false;
			}
		}
	}
    while(1){
        cin>>n;
        if(n==0)break;
		ans=0;
		co=0;
		for(int i=0;ans<n;i++){
			if(flag[i]==true){
				ans++;
				co+=i;
			}
		}
		cout<<co<<endl;
	}
}

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

using namespace std;

const int MX = 300001;
bool chck[MX];
int idx[MX];

int main()
{
    int n, q, inp, lim;

    cin >> n >> q;
    lim = 0;
    while (n--) {
        cin >> inp;
        chck[inp] = true;
        lim = max(lim, inp);
    }
    
    int pre = 0;
    for (int i = 1; i <= lim; i++) {
        if (chck[i]) {
            idx[i] = pre;
            pre = i;
        }
        else
            idx[i] = pre;
    }
        

    while (q--) {
        int s = lim;
        int ans = 0;
        cin >> inp;

        while (s > 0) {
            ans = max(ans, s % inp);
            
            s = idx[s - (s % inp)];
        }
        cout << ans << endl;
    }

    return 0;
}

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

using namespace std;

int main()
{
//    freopen("in.txt","r",stdin);

    string s;
    while(cin>>s)
    {
        if(s=="-")
            break;
        int m;
        cin>>m;

        int len=s.length();
        int c1=0;
        while(m--)
        {
            int n;
            cin>>n;
            int cur=c1;
            for(int i=cur; i<n+cur; i++)
            {
                s+=s[i];
//                cout<<s<<endl;
                c1++;
            }
        }
        for(int i=c1; i<c1+len; i++)
            cout<<s[i];
        cout<<endl;
    }
}



Measured memory_bytes: 3176
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long hxtype;
typedef pair<int,int>pii;
#define rep(i,l,r) for(i=(l);i<=(r);++i)
#define per(i,l,r) for(i=(l);i>=(r);--i)
#define REP(i,l,r) for(i=(l);i< (r);++i)
#define PER(i,l,r) for(i=(l);i> (r);--i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
const ll p=998244353ll;
const int N=100005;
vector<pii>e[N];
pii ed[N];
int d[N],vis[N];
void dfs(int v){
	vis[v]=1;
	int s=e[v].size(),u,dv=d[v],w;
	while(s--)if(!vis[u=e[v][s].fi]){
		dfs(u);
		if(d[u]){
			dv^=1;
			w=e[v][s].se;
			swap(ed[w].fi,ed[w].se);
		}
	}
	d[v]=dv;
}
int main(){
	int n,m,i,v,u;
	scanf("%d%d",&n,&m);
	rep(i,1,m){
		scanf("%d%d",&v,&u);
		d[v]^=1;
		e[v].push_back(mp(u,i));
		e[u].push_back(mp(v,i));
		ed[i]=mp(v,u);
	}
	rep(i,1,n)if(!vis[i]){
		dfs(i);
		if(d[i]){putchar('-');putchar('1');return 0;}
	}
	rep(i,1,m)printf("%d %d\n",ed[i].fi,ed[i].se);
	return 0;
}

Measured memory_bytes: 14720
import sys

N,C = map(int,input().split())
STC = []
for _ in range(N):
  s,t,c = map(int,sys.stdin.readline().split())
  STC.append([s,t,c])
STC.sort()

rs = [[STC[0][1],STC[0][2]]]
for i in range(1,N):
  len_rs = len(rs)
  
  min_idx = None
  for j in range(len_rs):
    if rs[j][1] != STC[i][2]: tmp_stc_r = STC[i][0] - 0.5
    else: tmp_stc_r = STC[i][0]
 
    if rs[j][0] <= tmp_stc_r:
      if min_idx is None: min_idx = j
      else:
        if rs[j][0] < rs[min_idx][0]: min_idx = j

  if min_idx is None: rs.append([STC[i][1], STC[i][2]])
  else: rs[min_idx] = [STC[i][1], STC[i][2]]
  
print(len(rs))

Measured memory_bytes: 21744
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)
#define outl(x) cout<< (x) << '\n'
#define fi first
#define se second
using ll= long long;
using namespace std;
using pii = pair<int,int>;

int a, b, c;
int X, Y;

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

   cin >> a >> b >> c >> X >> Y;

   int c2 = c*2;
   int minv = min(X, Y);

   int x_cost = min(c2, a);
   int y_cost = min(c2, b);

   ll ans = (ll)X * x_cost + (ll)Y * y_cost;

   {
      ll tmp = c2 * X;
      if (Y > X) {
         tmp += y_cost * (Y-X);
      }
      ans = min(ans, tmp);
   }

   {
      ll tmp = c2 * Y;
      if (X > Y) {
         tmp += x_cost * (X-Y);
      }
      ans = min(ans ,tmp);
   }

   outl(ans);

}



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

using namespace std;

constexpr int64_t modulo = UINT64_C(1000000007);

int64_t solve(int n, int m) {
  if (n < m) {
    std::swap(n, m);
  }
  if (n - m >= 2) {
    return 0;
  }
  int64_t ret = 1;
  for (int i = 2; i <= m; i++) {
    ret *= i;
    ret %= modulo;
  }
  ret *= ret;
  ret %= modulo;
  if (n == m) {
    ret *= 2;
  } else {
    ret *= n;
  }
  ret %= modulo;
  return ret;
}

int main() {
  int n, m;
  std::cin >> n >> m;
  std::cout << solve(n, m) << std::endl;
  return 0;
}

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

int dp[501][501];

int main(){
    int n,m,q;
    cin >> n >> m >> q;
    vector<P> LR;
    vector<P> RL;
    rep(i,m){
        int l,r;
        cin >> l >> r;
        P p(l,r);
        P q(r,l);
        LR.push_back(p);
        RL.push_back(q);
    }
    sort(LR.begin(),LR.end());
    sort(RL.begin(),RL.end());

    for(int l=1; l<=n; ++l){
        int ind=0;
        for(int r=l; r<=n; ++r){
            dp[l][r]=dp[l][r-1];
            while(RL[ind].first<=r){
                if(RL[ind].second>=l) dp[l][r]++;
                ind++;
            }
        }
    }

    rep(i,q){
        int l,r;
        cin >> l >> r;
        cout << dp[l][r] << endl;
    }

}

Measured memory_bytes: 5220
#include <bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
const ll INF = ll(1e9);
const int N = 1e5 + 5;
const ll mod = 1000000007 ;
using namespace std;

ll dp[105][N];

int main() {


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


	ll tc = 1;

	// cin >> tc;
	while (tc--) {

		ll n, i, j, a, b, c, k, W;
		cin >> n >> W;

		ll w[n], v[n];

		for (i = 0; i < n; i++) {
			cin >> w[i] >> v[i];
		}

		for (j = 1; j <= W; j++) {
			if (j >= w[0])
				dp[0][j] = v[0];
		}


		for (i = 1; i < n; i++) {
			for (j = 1; j <= W; j++) {
				if (j >= w[i])
					dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j - w[i]] + v[i]);
				else
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
			}
		}


		// for (i = 0; i < n; i++) {
		// 	for (j = 1; j <= W; j++) {
		// 		cout << dp[i][j] << " ";
		// 	}

		// 	cout << endl;
		// }

		// cout << endl;
		cout << dp[n - 1][W] << endl;


	}

}

Measured memory_bytes: 80128
#include<bits/stdc++.h>
#define INF     1e9
#define ld      long double
#define lli     long long int
#define PI 	    acos(-1)
#define read    freopen("in.txt","r",stdin)
#define uu		first
#define vv		second
#define write   freopen("out.txt","w",stdout)
#define pii     pair<int,int>
using namespace std;
int n,m,a,b,ara[200005];
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++) {
        scanf("%d %d",&a,&b);
        if(a==1 || a==n) ara[b]++;
        else if (b==1 || b==n) ara[a]++;
        if(ara[a]==2 || ara[b]==2) {
            printf("POSSIBLE\n");
            return 0;
        }
    }
    printf("IMPOSSIBLE\n");
    return 0;
}


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

  int  H, W ,N ;
  cin  >> H >> W >> N ;
  int A = max(H,W) ;
  int B = min(H,W) ;
  rep(i,B+1){
    if(A*i>=N){
      cout << i << endl;
      return 0 ;
    }
  }
}

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

int main(){
  int N;
  cin>>N;
  vector<int> A(N);
  vector<vector<int>> x(N,vector<int>(N)),y(N,vector<int>(N));
  for(int i=0;i<N;++i){
    cin>>A.at(i);
    for(int j=0;j<A.at(i);++j){
      cin>>x.at(i).at(j)>>y.at(i).at(j);
    }
  }

  int count=0;
  for (int tmp = 0; tmp < (1 << 15); tmp++) {
    bitset<15> s(tmp);
    bool frag=true;
    int sub_count=0;
    for(int i=0;i<N;++i){
      if(s.test(i)){
        ++sub_count;
        for(int j=0;j<A.at(i);++j){
          if(s.test(x.at(i).at(j)-1)!=y.at(i).at(j)){
            frag=false;
          }
        }
      }
    }

    if(frag){
      count=max(count,sub_count);
    }
  }

  cout<<count<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define nl '\n'
typedef long long ll;
typedef long double ld;
//////////////////////////////////////////////////////////////////////



int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  
  ll N,h,n,w;
  cin>>N;
  for(h=1;h<=3500;h++)
    for(n=1;n<=3500;n++){
      ll num = N*h*n;
      ll den = 4*h*n-N*(h+n);
      if ( den != 0 and num % den == 0
	   and num/den > 0 ) {
	cout << h << ' ' << n << ' ' << num/den << endl;
	return 0;
      }
    }
  
  return 0;
};


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <algorithm>
//#include <cstdio>
//#include <functional>
#include <iostream>
//#include <cfloat>
//#include <climits>
//#include <cstdlib>
//#include <cstring>
#include <cmath>
//#include <map>
//#include <queue>
//#include <set>
//#include <sstream>
//#include <stack>
//#include <string>
//#include <time.h>
#include <vector>
//#include <random>
//#include <unordered_set>
//#include <complex>
//#include <string.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define LL long long
#define pii pair<int,int>

using namespace std;
const int MOD=1e5+10;

int main()
{
	int n,a,b,h[MOD];
	 
	cin>>n>>a>>b;
	int hi=0;
	rep(i,n) {
		cin>>h[i];
		hi=max(hi,h[i]);
	}
	
	int lb=0;//(hi+a-1)/a;
	int ub=1e9;//(hi+b-1)/b;
	
	while(lb<ub) {
		LL mid=(lb+ub)/2;
		LL count=0; 
		rep(i,n){
			LL temp=h[i]-(mid*b); //按mid轮*b先消 
			if(temp<=0) continue; //已消掉 
			count+= (temp+a-b-1)/(a-b); //该点至少需要几轮a 
		}
		if(count<=mid){//mid轮可以完成
			ub=mid; 
			continue;
		} 
		lb=mid+1;
	}
	cout<<lb;
    rt0;
}


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

long long mul(long long x){
  if(x == 1) return 1LL;
  return (x*mul(x-1))%1000000007;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n, m;
  cin >> n >> m;
  if(abs(n-m) >= 2){
    cout << 0 << endl;
    return 0;
  }
  long long res = (mul(n)*mul(m))%1000000007;
  if(m == n) res = res*2%1000000007;
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
int main(void)
{
    int x, y, i;
    scanf("%d%d", &x, &y);
    
    int g1[7] = {1,3,5,7,8,10,12};
    int g2[4] = {4,6,9,11};
    
    int a = 0, b = 0;
    for(i=0; i<7; i++){
        if(g1[i] == x)
            a++;
        if(g1[i] == y)
            b++;
    }

    int c = 0, d = 0;
    for(i=0; i<4; i++){
        if(g2[i] == x)
            c++;
        if(g2[i] == y)
            d++;
    }
    if(a > 0 && b > 0 || c > 0 && d > 0)
        puts("Yes");
    else
        puts("No");

    return 0;
}


Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a[]=new int[3];
		a[0]=scan.nextInt();
		a[1]=scan.nextInt();
		a[2]=scan.nextInt();
		Arrays.sort(a);
		System.out.println(a[0]+a[1]);
	}
}

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

int sign(long long int num) {
  if (num==0) {
    return 0;
  }
  else {
    return num/abs(num);
  }
}

int main() {
  int n;
  cin >> n;
  vector<long long int> list(n);
  for (int i=0;i<n;i++) {
    cin >> list.at(i);
  }
  long long int count1=0,count2=0,sum=0;
  for (int i=0,s=1;i<n;i++) {
    sum+=list.at(i);
    if(sum*s<=0) {
      count1+=abs(sum)+1;
      sum=s;
      //cout << "1 " << count1 << endl;
    }
    //cout << sum << endl;
    s*=-1;
  }
  sum=0;
  for (int i=0,s=-1;i<n;i++) {
    sum+=list.at(i);
    if(sum*s<=0) {
      count2+=abs(sum)+1;
      sum=s;
      //cout << "2 " << count2 << endl;
    }
    //cout << sum << endl;
    s*=-1;
  }
  
  cout << min(count1,count2) << endl;
}


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

int main(){
	int x,y;
	cin>>x>>y;
	int a=y/2;
	if(a>=x && a<=2*x && y%2==0){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	
	
	return 0;
}


Measured memory_bytes: 3668
#include <stdio.h>

using namespace std;

int main(){
	int a,b,c,count = 0;
	scanf("%d %d %d",&a,&b,&c);
	for(int i = a; i <= b; i++){
		if(c%i == 0) count++;
	}
	printf("%d\n",count);
}


Measured memory_bytes: 2732
#include<bits/stdc++.h>
using namespace std;
const int maxn=1050;
int a[maxn],n,tmp[maxn],c[maxn];

int main(){
    cin >> n;
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=n;i;i--){
        int pos=0;
        for (int j=1;j<=i;j++) if (a[j]==j) pos=j;
        if (!pos) {puts("-1");return 0;}
        c[i]=a[pos];
        for (int j=pos;j<i;j++) a[j]=a[j+1];
    }
    for (int i=1;i<=n;i++) printf("%d\n",c[i]);
    return 0;
}


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

int main() {
    char s[101], p[101], ring[201];
    scanf("%s %s", s, p);

    strcpy(ring, s);
    strcat(ring, s);

    if (strstr(ring, p) == NULL) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }

    return 0;
}


Measured memory_bytes: 3252
#include <iostream>
#include <string>
using namespace std;
#define REP(i,to) for(i=0;i<(to);i++)

int main() {
	int i, j, k, l;
	string S; cin >> S;
	int K; cin >> K;
	char ans;

	REP(i, 100) {
		if (S[i] != '1') {
			ans = S[i];
			break;
		}
	}

	if (ans == '\0') ans = '1';
	else if (i != 0 && i + 1 > K) ans = '1';

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256