akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
#include <atcoder/all>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define ALL(v) v.begin(),v.end()
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; }
#define DEBUG_VLL(vec) for(int sz=0;sz<int(vec.size());sz++) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

using mint = atcoder::modint998244353;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    V<mint> a(n), b(m);
    for (int i = 0; i < n; i++) {
        ll ain; cin >> ain;
        a[i] = ain;
    }
    for (int i = 0; i < m; i++) {
        ll bin; cin >> bin;
        b[i] = bin;
    }

    V<mint> c = atcoder::convolution(a, b);
    for (int i = 0; i < int(c.size()); i++) cout << c[i].val() << (i == int(c.size()) - 1 ? '\n' : ' ');
    return 0;
}


Measured memory_bytes: 19028
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;cin>>n;
  ll a[n];
  ll i,j,k;
  for(i=0;i<n;i++) cin >> a[i];
  ll dp[n+1][2];
  memset(dp,0,sizeof(dp));
  for(i=0;i<n;i++){
    if(a[i]){
      if(a[i]%2){
	if(dp[i][1]>0) dp[i+1][0]=dp[i][1]+a[i]/2+1;
	dp[i+1][1]=dp[i][0]+a[i]/2;
      }else{
	if(dp[i][1]>0) dp[i+1][1]=dp[i][1]+a[i]/2;
	dp[i+1][0]=dp[i][0]+a[i]/2;
      }
    }else{
      dp[i+1][0]=max(dp[i][0],dp[i][1]);
    }
    //cout << dp[i+1][0] << ":" << dp[i+1][1] << endl;
  }
  cout << max(dp[n][0],dp[n][1]) <<endl;
  return 0;
}


Measured memory_bytes: 2560
n = int(input())
s = input()

L = 0  # 左かっこの数
R = 0  # 右かっこの数
cnt = 0  # 左かっこ(の数に対応した、あるべき右かっこ)の数

for i in s:
    if i == "(":
        cnt += 1
    else:
        if cnt > 0:
            cnt -= 1
        else:  # あるべき右かっこの数が０以下のとき、足りてないのは左かっこ
            L += 1
R = cnt

print("("*L + s + ")"*R)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,A,B,C,D;
  cin >>N ;
  D = N % 10;
  C = ((N-D) % 100)/10;
  B = ((N-10*C-D) % 1000)/100;
  A = N /1000;
  if (A==B && B==C) {
   cout << "Yes" <<endl;
  }
   else if (B==C && C==D) {
   cout << "Yes" <<endl;
  }
   else  {
   cout << "No" <<endl;
  }
}

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

int c[1000006];
vector<int> V;
set<int> S;
multiset<int> T;

int N, A[200005];

int dp[200005];

int num[1000006];

int main(void) {
	cin >> N;
	int Am = 0;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		V.push_back(A[i]);
		S.insert(A[i]);
		T.insert(A[i]);
		Am = max(Am, A[i]);
		num[A[i]]++;
	}

	//sort(V.begin(), V.end());

	

	for(auto y: V){
		if (c[y] >= 1) { c[y] = 2; }
		else if (c[y] >= 0) { c[y]++;
		for (long long int j = y*2; j <= Am; j+=y) {
			c[(int) j] = -1;
		}
		}
	}

	for (int i = 1; i <= N;i++) {
		if (T.count(A[i]) >= 2) { continue; }
	}

	int ans = 0;

	for (int i = 1; i <= N; i++) {
		//if (T.count(A[i]) >= 2) { continue; }
		if (c[A[i]] == 1) { ans++; }
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 30352
///
// File:  b.go
// Author: ymiyamoto
//
// Created on Mon Apr  2 23:54:41 2018
//
package main

import (
	"fmt"
)

var N int
var A []int

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	fmt.Scan(&N)

	A := make([]int, N)
	count := 0
	num := 0
	for range A {
		var n int
		fmt.Scan(&n)
		if n == 0 {
			count += num / 2
			num = 0
		} else {
			num += n
		}
	}

	count += num / 2
	fmt.Println(count)
}


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

int main(){
    int D,G;
    int p[10] = {};
    int c[10] = {};

    cin >> D >> G;

    for(int i=0;i<D;i++){
        cin >> p[i] >> c[i];
    }
    int ans = 99999;
    for(int flag=0;flag < (1 << D); flag++){
        int sum = 0, rest_max = -1, num=0;
        for(int i=0;i<D;i++){
            if((flag >> i) & 1){
                sum += c[i]+100*(i+1)*p[i];
                num += p[i];
            }else{
                rest_max = i;
            }
        }
        if(G > sum){
            int need = (G - sum - 1)/(100*(rest_max+1)) + 1;
            if(need >= p[rest_max]){
                continue;
            }else{
                num += need;
            }  
        }
        //cout << num << endl;
        ans = min(ans,num);
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
use std::io::*;

fn main() {
  let stdin = stdin();
  let mut lines = stdin.lock().lines();

  let line = lines.next().unwrap().unwrap();
  let mut args = line.split_whitespace().map(|s| s.parse::<usize>().unwrap());
  let n = args.next().unwrap();
  let m = args.next().unwrap();

  let mut vec_a: Vec<Vec<usize>> = Vec::with_capacity(n);

  for line in lines.by_ref().take(n) {
    let line = line.unwrap();
    let v = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    vec_a.push(v);
  }

  let vec_b: Vec<usize> = lines.take(m).map(|l| l.unwrap().parse().unwrap()).collect();

  let stdout = stdout();
  let mut stdout = BufWriter::new(stdout.lock());

  let vec_c = vec_a.into_iter().map(|v| {
    v.into_iter().zip(&vec_b).fold(0, |acc, t| acc + t.0 * t.1)
  });

  for c in vec_c {
    writeln!(stdout, "{}", c).unwrap();
  }
}



Measured memory_bytes: 5048
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
int main(){int h,w; cin>>h>>w; char a[h][w]; int dp[h][w]; rep(i,h)rep(j,w) cin>>a[i][j],dp[i][j]=0; dp[0][0]=1; rep(i,h)rep(j,w){if(i>0) dp[i][j]+=dp[i-1][j];if(j>0) dp[i][j]+=dp[i][j-1];dp[i][j] %= 1000000007;if(a[i][j]=='#') dp[i][j]=0;} cout<<dp[h-1][w-1];}

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

int main() {
  int n;
  cin >> n;
  vector<int> l(n);
  for(int i; i<n; i++){
    cin >> l.at(i);
  }
  
  int ans=0, num=1;
  for(int j; j<n; j++){
    if(l.at(j)==num){
      num+=1;
    }
    else{
      ans+=1;
    }
  }
  
  if(num==1){
    cout << -1 << endl;
  }
  else{
    cout << ans << endl;
  }
}

Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
	long long n, a, b, s, t;
	while(~scanf("%lld %lld %lld", &n, &a, &b))
	{
		t = n/(a+b);
		s = t*a;
		if(n%(a+b)>a) s += a;
		else s += n%(a+b);
		printf("%lld\n", s);
	}
	return 0;
}

Measured memory_bytes: 504
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max(a * b, c * d) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
int mod = 2;
// constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

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

ll mod_pow(ll x, int n){
    if(n == 0)      return 1;

    ll res = 1;
    while(n > 0){
        if(n & 1)   res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

struct Combination{
    int sz;
    vector<ll> fact;
    vector<ll> ifact;

    Combination(int sz = 1e+5) : sz(sz) {
        fact = vector<ll>(sz + 1);
        ifact = vector<ll>(sz + 1);

        fact[0] = 1;
        for(ll i = 1; i <= sz; ++i){
            fact[i] = fact[i - 1] * i % mod;
        }

        ifact[sz] = mod_pow(fact[sz], mod - 2);
        for(ll i = sz; i > 0; --i){
            ifact[i - 1] = ifact[i] * i % mod;
        }
    }

    ll get_combination(int n, int r){
        if(n < 0 || r < 0 || n < r)     return 0;

        return fact[n] * ifact[r] % mod * ifact[n - r] % mod;
    }
};

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

    int p;
    cin >> p;
    mod = p;
    vector<ll> b(p, 0);
    Combination c(p - 1);
    for(int i = 0; i < p; ++i){
        int a;
        cin >> a;
        if(a == 0)  continue;
        b[0] = (b[0] + 1) % p;
        ll val = -i % p;
        if(val < 0) val += p;
        for(int j = 0; j < p; ++j){
            b[j] -= c.get_combination(p - 1, j) * mod_pow(val, p - 1 - j) % p;
            if(b[j] < 0)    b[j] += p;
        }
    }
    for(int i = 0; i < p; ++i){
        cout << b[i];
        cout << ((i == p - 1) ? '\n' : ' ');
    }
}

Measured memory_bytes: 3704
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=200050;
char s[maxn],t[maxn];
int a[30],b[30];
int main(){
	scanf("%s%s",s,t);
	int lens=strlen(s),lent=strlen(t);
	if(lens!=lent){
		cout<<"No"<<endl;
		return 0;
	}
	for(register int i=0;i<lens;i++){
		a[s[i]-'a']++,b[t[i]-'a']++;
	}
	sort(a,a+30);
	sort(b,b+30);
	for(register int i=0;i<30;i++){
		if(a[i]!=b[i]){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

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

int64_t LCM(int x, int y)
{
  return x / __gcd(x, y) * y;
}

int f(int x)
{
  int ret = 0;
  while (x % 2 == 0)
  {
    x /= 2;
    ret++;
  }
  return ret;
}

int main()
{
  int64_t N, M;
  cin >> N >> M;
  vector<int64_t> A(N);
  for (int i = 0; i < N; i++)
  {
    cin >> A.at(i);
    A.at(i) /= 2;
  }
  int t = f(A[0]);
  for (int i = 0; i < N; i++)
  {
    if (f(A[i]) != t)
    {
      cout << 0 << endl;
      return 0;
    }
    A[i] >>= t;
  }
  M >>= t;
  int64_t l = 1;
  for (int i = 0; i < N; i++)
  {
    l = LCM(l, A[i]);
    if (l > M)
    {
      cout << 0 << endl;
      return 0;
    }
  }
  int64_t ans = (M / l + 1) / 2;
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
using namespace std;

struct room{
  int roomnum;
  bool visited;
  
  bool operator>(const room compared) const
  {
    return roomnum > compared.roomnum;
  }
  bool operator<(const room compared) const
  {
    return roomnum < compared.roomnum;
  }
};

struct compar{
  long long int cost;
  int  loc_x, loc_y;
  bool is_ns;
  
  bool operator>(const compar compared) const
  {
    return cost > compared.cost;
  }
  bool operator<(const compar compared) const
  {
    return cost < compared.cost;
  }
};

int m, n, k;
vector<room> ns[100001], ew[100001];
priority_queue<compar, vector<compar>, greater<compar> > sr;

long long int dijk()
{
  if(!ns[1].size())
    return -1;
  
  compar start = {(ns[1].begin())->roomnum - 1, 1, (ns[1].begin())->roomnum, true};
  sr.push(start);
  
  while(!sr.empty()){
    compar now = sr.top();
    sr.pop();
    
    if(now.loc_x == m && now.loc_y == n)
      return now.cost;
    
    vector<room>::iterator p;
    if(now.is_ns){
      room pp = {now.loc_y, false};
      p = lower_bound(ns[now.loc_x].begin(), ns[now.loc_x].end(), pp);
      
      if(!p->visited){
	p->visited = true;
	if(p != ns[now.loc_x].begin()){
	  compar next = {now.cost + now.loc_y - (p - 1)->roomnum, now.loc_x, (p - 1)->roomnum, true};
	  sr.push(next);
	}
	if(p != ns[now.loc_x].end() - 1){
	  compar next = {now.cost + (p + 1)->roomnum - now.loc_y, now.loc_x, (p + 1)->roomnum, true};
	  sr.push(next);
	}
	compar next = {now.cost + 1, now.loc_x, now.loc_y, false};
	sr.push(next);
      }
    }
    else{
      room pp = {now.loc_x, false};
      p = lower_bound(ew[now.loc_y].begin(), ew[now.loc_y].end(), pp);

      if(!p->visited){
	p->visited = true;
	if(p != ew[now.loc_y].begin()){
	  compar next = {now.cost + now.loc_x - (p - 1)->roomnum, (p - 1)->roomnum, now.loc_y, false};
	  sr.push(next);
	}
	if(p != ew[now.loc_y].end() - 1){
	  compar next = {now.cost + (p + 1)->roomnum - now.loc_x, (p + 1)->roomnum, now.loc_y, false};
	  sr.push(next);
	}
	compar next = {now.cost + 1, now.loc_x, now.loc_y, true};
	sr.push(next);
      }
    }
  }

  return -1;
}

int main()
{
  scanf("%d%d%d", &m, &n, &k);
  for(int i = 0; i < k; i++){
    int x, y;
    scanf("%d%d", &x, &y);
    room x_in = {y, false};
    ns[x].push_back(x_in);
    room y_in = {x, false};
    ew[y].push_back(y_in);
  }

  room x_in = {n, false};
  ns[m].push_back(x_in); 
  room y_in = {m, false};
  ew[n].push_back(y_in);
  
  for(int i = 1; i <= m; i++)
    sort(ns[i].begin(), ns[i].end());
  for(int i = 1; i <= n; i++)
    sort(ew[i].begin(), ew[i].end());
  
  printf("%lld\n", dijk());
  return 0;
}

Measured memory_bytes: 16228
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <utility>

using namespace std;

int main()
{
    int N;
    cin>>N;
    string S;
    cin>>S;

    map<pair<string,string>, int> M;

    for (int b=0; b<1<<N; b++)
    {
        string sr;
        string sb;
        for (int i=0; i<N; i++)
            (b>>i&1 ? sr : sb) += S[i];
        M[make_pair(sr,sb)]++;
    }

    long long ans = 0;
    for (int b=0; b<1<<N; b++)
    {
        string sr;
        string sb;
        for (int i=0; i<N; i++)
            (b>>i&1 ? sr : sb) += S[2*N-i-1];
        ans += M[make_pair(sr,sb)];
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 91904
from itertools import combinations
n = int(input())
l = list(map(int,input().split()))
c = combinations(l,3)
ans=0
for (a,b,c) in c:
  if a+b>c and b+c>a and c+a>b and a!=b and b!=c and a!=c:
    ans+=1
print(ans)

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

vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int h, w, ch, cw, dh, dw;
  cin >> h >> w >> ch >> cw >> dh >> dw;
  ch--;
  cw--;
  dh--;
  dw--;
  
  vector<vector<char>> s(h, vector<char>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> s[i][j];
    }
  }
  
  vector<vector<int>> d(h, vector<int>(w, 1e9));
  deque<tuple<int, int, int>> dq;
  dq.push_front(make_tuple(0, ch, cw));
  d[ch][cw] = 0;
  
  while (!dq.empty()) {
    auto [dist, nowx, nowy] = dq.front();
    dq.pop_front();
    for (int i = 0; i < 4; i++) {
      int nx = nowx + dx[i], ny = nowy + dy[i];
      if (0 <= nx && nx < h && 0 <= ny && ny < w && s[nx][ny] == '.' && d[nx][ny] > dist) {
        d[nx][ny] = dist;
        dq.push_front(make_tuple(dist, nx, ny));
      }
    }
    for (auto i : {-2, -1, 0, 1, 2}) {
      for (auto j : {-2, -1, 0, 1, 2}) {
        int nx = nowx + i, ny = nowy + j;
        if (0 <= nx && nx < h && 0 <= ny && ny < w && s[nx][ny] == '.' && d[nx][ny] > dist + 1) {
          d[nx][ny] = dist + 1;
          dq.push_back(make_tuple(dist + 1, nx, ny));
        }
      }
    }
  }
  
  if (d[dh][dw] == 1e9) cout << -1 << '\n';
  else cout << d[dh][dw] << '\n';
}

Measured memory_bytes: 8584
import java.util.Scanner;


public class Main 
{

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		String N = sc.next();
		sc.close();
		
		int result = N.indexOf("9");
		
		if(result==-1)
		{
			System.out.println("No");
		}
		else
		{
			System.out.println("Yes");
		}

	}

}


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

ll ruijyo(int k) {
  ll tmp = 1;
  if (k == 0) {
    return 1;
  }
  else {
    rep(i, k) {
      tmp *= 10;
    }
    return tmp;
  }
}

int main() {
  vector<vector<int>> table(10, vector<int>(10));
  table = {{1,0,0,0,0,0,0,0,0,0},
           {1,2,0,0,0,0,0,0,0,0},
           {2,2,4,0,0,0,0,0,0,0},
           {4,4,4,8,0,0,0,0,0,0},
           {8,8,8,8,16,0,0,0,0,0},
           {16,16,16,16,16,32,0,0,0,0},
           {32,32,32,32,32,32,64,0,0,0},
           {64,64,64,64,64,64,64,128,0,0},
           {128,128,128,128,128,128,128,128,256,0},
           {256,256,256,256,256,256,256,256,256,512}};       
  string s;
  cin >> s;
  int n = s.size();
  ll ans = 0;
  rep(i, n) {
    rep(j, n) {
      //cout << s.at(j) << endl;
      char ss = s.at(j);
      int num; 
      num = (int)ss;
      int numm = num - 48;
      //cout << numm << endl;
      ans += table.at(i).at(j) * ruijyo(n - i - 1) * numm;
      //cout << table.at(i).at(j) * ruijyo(n - i - 1) * numm << endl;
    }
  }
  cout << ans << endl;
}      
 

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;

int main(){
    fast_io
   
    int n, k;
    cin>>n>>k;
    vector<ll> p(n), c(n);
    rep(i,n) {
      cin>>p[i];
      p[i]--;
    }
    rep(i,n) cin>>c[i];
    ll ans = -1e18;
    rep(si, n){
      int x = si;
      vector<int> s;
      ll tot = 0;
      while(1){
        x = p[x];
        s.push_back(c[x]);
        tot += c[x];
        // もとに戻ったら閉路なので終わり
        if(x == si) break;
      }
      int l = s.size();
      ll t = 0;
      rep(i,l){
        t += s[i];
        if(i+1 > k) break;
        ll now = t;
        if(tot > 0){
          ll e = (k-(i+1))/l;
          now += tot*e;
        }
        ans = max(ans, now);
      }
    }
    cout<<ans<<endl;
    return 0;
}


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

long n;
int c, m, a;
string s;

int main(){
	cin >> n;
	s = "";
	c = 1;
	do{
		m = abs(n) % 2;
		s = to_string(m) + s;
		n = (n-c*m)/2;
		c = -c;
	} while (n != 0);
	cout << s;
}

Measured memory_bytes: 256
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main()
{
    long long n,a,b;
    cin >> n >> a >> b;
    
    long long d=b-a;
    long long ans;
    if(d%2==0)
        ans = d/2;
    else
        ans = min(a-1, n-b) + 1 + d/2;
    
    std::cout << ans << std::endl;
}

// GCC reference:
//   https://gcc.gnu.org/

// C++ language references:
//   https://cppreference.com/
//   https://isocpp.org/
//   http://www.open-std.org/jtc1/sc22/wg21/

// Boost libraries references:
//   https://www.boost.org/doc/


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

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
#define RREP(i, n ,N) for(ll i = (N-1); i >= (n); i--)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll inf = 1e18;

ll N, D, A;
pair<ll, ll> XH[200010];
ll damage_imos[200010];
ll bomb_right_range[200010];
ll ans;
ll X[200010];
int main(){
	cin >> N >> D >> A;
	REP(i,0,N){
		cin >> XH[i].first >> XH[i].second;
		X[i] = XH[i].first;

	}
	sort(XH, XH+N);
	sort(X, X+N);

//	ll R = 1;
	REP(i,0,N){
		ll now=XH[i].first + 2*D;
		bomb_right_range[i] = upper_bound(X, X+N, now) - X - 1;
//		p(bomb_right_range[i]);
//		bool ok = false;
//		REP(j, R, N){
//			if(XH[j].first > now) {
//				bomb_right_range[i] = j-1;
//				ok = true;
//				R = j;
//				break;
//			}
//		}
//		if(!ok) bomb_right_range[i] = N-1;
	}

	REP(i,0,N){
		// calc
		ll now_damage = XH[i].second - damage_imos[i] * A;
		ll bomb_cnt = 0;
		if(now_damage > 0) bomb_cnt = (now_damage + A - 1) / A;
		ans += bomb_cnt;
		// update
		damage_imos[i] += bomb_cnt;
		damage_imos[bomb_right_range[i]+1]-= bomb_cnt;
		damage_imos[i+1] += damage_imos[i];
//		p(damage_imos[i]);
	}
	p(ans);
	return 0;
}

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

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define pii pair < int , int >
#define task "flight"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = 2e5 + 123;
const int mod = 1e9 + 7;
const int INF = 1e9 + 1;
const ll INFL = 3e18 + 1;
const double pi = acos(-1.0);

void files (string s) {
  if (fopen ((s + ".in").c_str(),"r")) {
  	freopen ((s + ".in").c_str(),"r", stdin);
    freopen ((s + ".out").c_str(),"w", stdout);
  }
}
    
int main () {
	files ("");

	char a, b;
	cin >> a >> b;	
	
	if(a > b) {
		cout << '>';	 	
	}
	if(a == b) {
		cout << '=';	 	
	}
	if(a < b) {
		cout << '<';	 	
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(){
    long long X;

    cin >> X;

    for(long long i=-200; i<=200; ++i){
        for(long long j=-200; j<=200; ++j){
            //long long calc = (i*i*i*i*i) - (j*j*j*j*j);
            long long calc = pow(i, 5) - pow(j, 5);
            if(calc == X){
                cout << i << ' ';
                cout << j << endl;
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 4084
import operator
h = {}   
while True:
    try:
        i = int(input())
        if i in h:
            h[i] += 1
        else:
            h[i] = 0
    except EOFError:
        break

h1=sorted(h.items(),key=operator.itemgetter(1),reverse=1)
val = h1[0][1]
h2 = sorted(filter(lambda x:x[1]==val, h1))
for i in h2:
    print(i[0])

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

signed main(){
  
  int T;
  cin>>T;

  while(T--){
    
    vector<int> A;
    
    int N = 0;
    
    while(1){
      int a;
      cin>>a;
      if( a == 0 ) break;
      A.push_back(a);
      if( a > 0 ) N++;
    }
    
    vector<int> G[N];
    
    typedef pair<int,int> P;
    
    vector<P> st;
    
    st.push_back( P( 0, A[0] ) );
    
    int next = 1;
    
    for(int i=1;i<(int)A.size();i++){
      
      if( A[i] > 0 ){
	
	int pre = st[(int)st.size()-1].first;
	
	G[pre].push_back( next );
	
	G[next].push_back( pre );
	
	st[(int)st.size()-1].second--;
	
	st.push_back( P( next, A[i] - 1 ) );
	
	next++;
	
      }else{
	
	int pre = st[(int)st.size()-1+A[i]].first;
	int node = st[(int)st.size()-1].first;
	
	G[pre].push_back( node );
	
	G[node].push_back( pre );
	
	st[(int)st.size()-1].second--;
	
	st[(int)st.size()-1+A[i]].second--;
	
      }
      
      while( (int)st.size() != 0 && st[(int)st.size()-1].second == 0 ){
	st.pop_back();
      }
      
    }
    
    for(int i=0;i<N;i++){
      
      cout<<i+1;
                  
      sort( G[i].begin(), G[i].end() );
      
      for(int j=0;j<(int)G[i].size();j++){
	cout<<' ';
	cout<<G[i][j]+1;
      }
      
      cout<<endl;
      
    }
    
  }
    
  return 0;
}



Measured memory_bytes: 3152
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

S=input()
T=input()
ans=0
for x,y in zip(S,T):
    if x!=y:
        ans+=1
print(ans)

Measured memory_bytes: 68336
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
long long  x,n=100;
using namespace std;
int main() {
    scanf("%lld", &x);
    for (int i = 1;; i++) {
        n = n*1.01;
        if (n >= x) { 
            printf("%d\n", i); break; 
        }
    }
    return 0;
}

Measured memory_bytes: 3200
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // dequef
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower

#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int k;
  cin >> k;
  int num = 7, cnt = 1;
  map<int, int> check;
  while(num %= k){
    if(check[num]){
      cout << -1 << endl;
      return 0;
    }
    check[num]++;
    cnt++;
    (num *= 10) += 7;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 50480
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();

		System.out.printf("%d %d %.10f\n", a/b,a%b,(double)a/(double)b);
	}
}



Measured memory_bytes: 26396
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;



int main(){
  int n,m;
  cin>>n>>m;// n桁，m個の条件
  vector<int> a(n);
  rep(i,n) a[i]=-1;
  

  if(n==1 && m==0){
    cout<<0<<endl;
    return 0;
  }
  
  
  rep(i,m){
    int s,c;
    cin>>s>>c;
    --s;
    if(n>1 && s==0 && c==0){//例外処理
      cout<<-1<<endl;
      return 0;
    }
    
    if(a[s]==-1 || a[s]==c){//未定or同一の場合は記入OK
      a[s]=c;
    }else{
      cout<<-1<<endl;
      return 0;
    }
    
  }

  rep(i,n){
    if(i==0 && a[i]==-1) a[0]=1;
    else if(a[i]==-1) a[i]=0;
    
    cout<<a[i];
    
    
  }
  
  return 0;
  
 
  
 
  
 
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import numpy as np

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


def solve(N: int):
    a = []
    for i in range(1,10):
        for j in range(1,10):
            a.append(i*j)
    b = list(set(a))
    if N in b:
        print(YES)
    else:
        print(NO)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


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

template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }
    
    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }
    
    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N; cin >> N;int Q; cin >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<int> lefts(Q), rights(Q), ids(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> lefts[i] >> rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return rights[i] < rights[j];});

    BIT<int> bit(N+5);
    vector<int> prev(1100000, -1);
    vector<int> res(Q, 0);
    int r = 0;
    for (auto i : ids) {
        for (; r < rights[i]; ++r) {
            bit.add(prev[a[r]]+2, r+2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i]+1, lefts[i]+2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}

Measured memory_bytes: 21728
"""
NTC here
"""
import sys
inp = sys.stdin.readline
def input(): return inp().strip()
flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())


def lin(): return list(map(int, input().split()))

# out = []
# range = xrange
# input = raw_input

def main():
    from bisect import bisect_right as br
    def find(a, b, c):
        sc = set(c)
        smc = len(c)
        ans = 0
        for i in a:
            for j in b:
                if j>i:
                    x = smc - br(c, j)
                    ans += x - (1 if (j-i)*2+i in sc else 0)
        return ans


    n = iin()
    s = input()
    dc = {'R':[], 'G':[], 'B':[]}
    for i in range(n):
        dc[s[i]].append(i)
    a, b, c = dc['R'], dc['B'], dc['G']
    ans = find(a, b, c) + find(a, c, b) + find(b, a, c) + find(b, c, a) + find(c, a, b) + find(c, b, a)
    print(ans)

main()
# threading.Thread(target=main).start()


Measured memory_bytes: 68588
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def sum_arithmetic_seq(a, d, n):
    return n * (2 * a + (n - 1) * d) // 2

def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

    B = [0] * N
    C = [0] * N
    for i in range(N):
        for j in range(i):
            if A[i] < A[j]:
                B[i] += 1
    for i in range(N):
        for j in range(N):
            if A[i] < A[j]:
                C[i] += 1

    ans = sum(B) * K
    ans %= MOD
    ans += sum_arithmetic_seq(0, sum(C), K)
    ans %= MOD
    print(ans)



if __name__ == '__main__':
    main()


Measured memory_bytes: 9288
#include <bits/stdc++.h>  // This will work only for g++ compiler.
#define for0(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
#define forab(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i) // closed interver from l to r r inclusive
#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i) // reverse 0 based.
#define forr1(i, n) for (int i = (int)(n); i >= 1; --i) // reverse 1 based
#define pb push_back
#define fi first
#define se second
#define __builtin_popcount(x) ones(x)
#define __builtin_popcountl(x) onesl(x)
#define __builtin_popcountll(x) onesll(x)// to be used with algorithms that processes a container Eg: find(all(c
#define all(x) (x).begin(), (x).end() //Forward traversal
#define rall(x) (x).rbegin, (x).rend() //reverse traversal
#define tr(c,i) for(__typeof__((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define sz(a) int((a).size())
#define Fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define InputOuput freopen("input.txt", "r", stdin); freopen("output.txt","w", stdout);
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
ll inf = 1e9 +5;

int main(){
    //InputOuput;
    Fast;
    ll n ,tot; cin >> n >> tot ;
    vll w(n+1,0);
    vll v(n+1, 0);
    ll mxval = 0;
    for1(i,n) {
        cin >> w[i] >> v[i];
        mxval += v[i];

    }
    vll dp(mxval+1, inf);
    dp[0] = 0 ;
    for1(i,n){
        for(int val = mxval - v[i]; val>=0 ; val--){
            dp[val + v[i]] = min(dp[val+v[i]] , dp[val]+w[i]);
        }
    }
    ll ans = 0;
    for(ll i = 0 ; i<= mxval; i++){
        if(dp[i]<=tot){
            ans = max(ans, (ll)i);
        }
    }
    cout << ans <<'\n';
    return 0;

}

Measured memory_bytes: 3996
import java.util.*;

public final class Main {

    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);

        int n  = s.nextInt();

        int m = s.nextInt();

        long mod = 1000000000 + 7;

        long[] x = new long[n];

        for (int i = 0; i < n; i++) {

            x[i] = s.nextInt();
        }


        long[] y = new long[m];

        for (int i = 0; i < m; i++) {

            y[i] = s.nextInt();
        }


        long sum_interval = 0;

        long before_inteval = 0;
        for (int i = 1; i< m; i++) {

            long interval = y[i] - y[i-1];

            long now = before_inteval + (interval*i)%mod;

            before_inteval = now;

            sum_interval += now;
        }

        sum_interval = sum_interval %mod;

        long result = 0;
        long before_sum = 0;
        for (int i = 1; i < n; i++) {

            long x1 = x[i];

            long x2 = x[i-1];

            long xint = x1-x2;

            long now = xint * sum_interval;

            long r = (now%mod*i)%mod + before_sum;

            before_sum = r;

            result += r;
        }

        System.out.print(result%mod);
    }


}

Measured memory_bytes: 65268
#include<bits/stdc++.h>
using namespace std;
int main() {
        int sx, sy, tx, ty;
        cin >> sx >> sy >> tx >> ty;
        const int dx=tx-sx,dy=ty-sy;
        cout<<string(dy,'U')<<string(dx,'R');
        cout<<string(dy,'D')<<string(dx,'L');
        cout<<'L'<<string(dy+1,'U')<<string(dx+1,'R')<<'D';
        cout<<'R'<<string(dy+1,'D')<<string(dx+1,'L')<<'U'<<endl;
        return 0;
}


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

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def each_attend(anm, held):
    n = len(anm)
    m = len(anm[0])
    atte = []
    for i in range(n):
        aim = anm[i]
        for k in aim:
            if k in held:
                break
        atte.append(k)
    return atte

def main():
    n, m = map(int, input().split())
    anm = []
    for i in range(n):
        aim = list(map(int, input().split()))
        anm.append(aim)

    held = set(range(1, m + 1))
    res = HUGE
    while len(held) > 0:
        atte = each_attend(anm, held)
        num_atte = {k: 0 for k in range(1, m + 1)}
        for k in atte:
            num_atte[k] += 1
        ma = max(num_atte.values())
        res = min(res, ma)
        popest_sports = set(filter(lambda k: num_atte[k] == ma, held))
        held -= popest_sports
    print(res)

main()


Measured memory_bytes: 4872
#include<bits/stdc++.h>            //  IT'S NEVER TOO LATE...
    	using namespace std;
        #include<math.h>
    	#define ll long long
    	#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
        #define forn(i, n) fore(i, 0, n)
        #define fori(i, l, r) fore(i, l, (r) + 1)
        #define sz(v) int((v).size())
        #define all(v) (v).begin(), (v).end()
        #define pb push_back
        #define mp make_pair
        #define ff first
        #define ss second

        const double PI = atan(1)*4;

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

    	
    	vector<int> ar[1000001];
        vector<pair<int,int>> path;
        int vis[1000001],dis[1000001];

        /*void dfs(int node)
        {
            vis[node]=1;

            for(int child : ar[node])
            {
                if(vis[child]==0)
                {
                    dis[child]=dis[node]+1;
                    dfs(child);
                }
            }
        }*/

    /*    void bfs(int i)
        {
            queue<int> q;
            q.push(i);
            vis[i]=1;
            dis[i]=0;

            while(!q.empty())
            {
                int curr=q.front();
                q.pop();

                for(int child : ar[curr])
                    if(vis[child]==0)
                    {
                        q.push(child);
                        dis[child]=dis[curr]+1;
                        vis[child]=1;
                    }
            }
        }*/

        bool isprime(int n)
        {
            for(int i=2;i*i<=n;i++)
                if(n%i==0)
                    return false;
            return true;
        }

        bool comp(pair<int,int> a, pair<int,int> b)
        {
            return b.ff < a.ff ;
        }

        int modpow(int b,int p,int m)
        {
            if(p==0) return 1%m;
            if(p%2) return (b*modpow(b,p-1,m))%m;
            int u=modpow(b,p/2,m);
            return (u*u)%m;
        }

    	int main()  
    	{
    		int t=1;
    		//cin>>t;
    		
    		while(t--)
    		{
                int a,b,m;
                double h;
                cin>>a>>b>>h>>m;

                h+=(double)m/60;
                double ans,ang; 
                ang=(double)(PI*h)/6 - (PI*m)/30 ;
                if(ang<0)
                    ang*=-1;
                ans=pow(a,2) + pow(b,2) - (double)2*a*b*cos(ang) ;
                ans=(double)sqrt(ans);             

                cout<<fixed<<setprecision(12)<<ans;
            }
            return 0;
    	}

        //              NOW IT'S TIME TO WAKE UP...

Measured memory_bytes: 27652
import math
a,b,C = map(int,input().split())
C = math.radians(C)
S = (1/2)*a*b*math.sin(C)
print(S)
c = math.sqrt(a**2+ b**2 -2*a*b*math.cos(C))
L = a + b + c
print(L)
h = (math.sin(C)) * b
print(h)


Measured memory_bytes: 5704
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	int Total = 0;
	int *line = new int[n];
	for (int i = 0; i < n; ++i) {
		cin >> line[i];
	}
	long long ans = ((long long)1 << 63) - 1;
	bool plusf = true;
	for (int i = 0; i < 2; ++i) {
		Total = 0;
		long long dn = 0;
		for (int j = 0; j < n; ++j) {
			if (j % 2 == 1 !=plusf) {
				Total += line[j];
				if (Total <= 0) {
					dn += -Total + 1;
					Total = 1;
				}
			}
			else {
				Total += line[j];
				if (Total >= 0) {
					dn += Total + 1;
					Total = -1;
				}
			}
		}
		plusf = !plusf;
		ans = min(ans, dn);
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
    int N;
    cin >> N;
    long long a[300010];
    long long ans = 0;
    for (int i=1; i<3*N+1; i++) cin >> a[i];
    sort(a+1, a+3*N+1);
    for (int i=N+1; i<3*N; i += 2){
        ans += a[i];
    }
    cout << ans << endl;
    return 0;
}


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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)

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

const int INF = 100;

int n;
int a[210];

int main(void) {
    cin >> n;
    REP(i, n) cin >> a[i];

    int res=INF;
    int cnt;
    REP(i, n) {
        cnt=0;
        while(1){
            if(a[i]%2!=0) break;
            a[i]/=2;
            cnt++;
        }
        if(res>cnt){
            res=cnt;
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f3f
#define pi 3.1415926535898
using namespace std;
const ll mod=1e9+7;
const ll N=1e6+10;
map <int,int> m;
int mp[1000050];
ll pows(ll n,ll a)
{
    ll ans=1;
    while(a)
    {
        if(a&1)
        {
            ans=ans*n%mod;
        }
        n=n*n%mod;
        a>>=1;
    }
    return ans;
}
ll inv(ll x)
{
    return pows(x,mod-2);
}
void init()
{
    for(int i=2;i<N;i++)
    {
        if(mp[i])
            continue;
        for(int j=i;j<N;j+=i)
        {
            mp[j]=i;
        }
    }
}
void update(ll x)
{
    while(x!=1)
    {
        int a=mp[x];
        int cnt=0;
        while(x%a==0)
        {
            x/=a;
            ++cnt;
        }
        m[a]=max(m[a],cnt);
    }
}
int main()
{
    init();
    int n;
    cin>>n;
    int a[n]={};
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        update(a[i]);
    }
    ll l=1;
    for(auto i : m)
    {
        l*=pows(i.first,i.second);
        l%=mod;
    }
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        ans+=l*inv(a[i]);
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 7808
#include<bits/stdc++.h>
using namespace std;
int main(){
  int i;
  int z;
  string s = "abcdefghijklmnopqrstuvwxyz";
  int min_num[26];


  cin >> z;
  for (i = 0; i<z;i++){
    string s_in;
    cin >> s_in;
    int min_s[26] = {0};

    for (int x = 0;x< (int)s.size();x++){
      for (int q = 0; q < (int)s_in.size();q++){
        if(s[x] == s_in[q]){
          min_s[s[x]-'a']++;
        }
      }
    }
    if(i == 0){
      for (int o = 0;o<26;o++){
        min_num[o] = min_s[o];
      }
    }
    for (int o = 0; o < 26; o++){
      /* code */
      min_num[o] = min(min_num[o], min_s[o]);
    }
  }
  for (i = 0;i < 26;i++){
    for(int q = 0; q < min_num[i]; q++){
    cout << s[i];
  }
  }
  cout << endl;
  return 0;
}


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

double calc(int t,int x){
 return t-x*0.006 ;
}

int main()
{
  int n,t,a ;
  cin >> n >> t >> a;
  int h;

  double dif ;
  int ans;
  for(int i=0;i<n;i++){
    cin >> h;
    if(i==0){
       dif = abs(a-calc(t,h));
       ans = i ;
       continue;
    }
    if(abs(a-calc(t,h))<dif){
      dif = abs(a-calc(t,h));
      ans = i ;
    }
  }
   cout << ans+1 << "\n" ;

  return 0;
}


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

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

  int K;
  cin >> K;
  long long ans = 0;
  for(int i = 1; i <= K; i++){
    for(int j = 1; j <= K; j++){
      for(int t = 1; t <= K; t++){
        ans += __gcd(i, __gcd(j, t));
      }
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

string S;
int A, B, C, D;

int main(void){
    
    cin >> S;
    A = S[0] - '0', B = S[1] - '0', C = S[2] - '0', D = S[3] - '0';
    
    for(int i = 0; i < 2; ++i){
        for(int j = 0; j < 2; ++j){
            for(int k = 0; k < 2; ++k){
                int ans = A;
                if(i) ans += B;
                if(!i) ans -= B;
                if(j) ans += C;
                if(!j) ans -= C;
                if(k) ans += D;
                if(!k) ans -= D;
                if(ans == 7){
                    printf("%d%c%d%c%d%c%d=7\n", A, ((i) ? '+' : '-'), B, ((j) ? '+' : '-'), C, ((k) ? '+' : '-'), D);
                    return 0;
                }
            }
        }
    }
    
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<cstring>

using namespace std;

int main()
{
    string s1="ABC";
    string s2="ARC";
    string S;
    cin>>S;
    if(S==s1)
        cout<<s2<<endl;
    else
        cout<<s1<<endl;
    return 0;
}


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

#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
#define endl "\n" 
#define all(c) c.begin(),c.end()
#define present(c,element) (c.find(element)!=c.end())
#define cpresent(c,element) (find(c,element)!=c.end())
#define forr(i,a,b) for(int i=a;i<int(b);i++)
#define tr(i,a) for(auto i:a)
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
const double PI=acos(-1);
const ll mod=1e9+7;





int32_t main()
{
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

int test=1;
//cin>>test;
while(test--)
{
	string s, t, x="";
	cin>>s>>t;
	int lcs[s.size()+1][t.size()+1];
	memset(lcs,0,sizeof(lcs));
	for(int i=1;i<=s.size();i++)
	{	
		for(int j=1;j<=t.size();j++)
		{
			if(s[i-1]==t[j-1]){
				lcs[i][j]=1+lcs[i-1][j-1];
			}
			else 
				lcs[i][j]=max(lcs[i-1][j], lcs[i][j-1]);
		}

	}
	int i=s.size(), j=t.size();
	while(i>0&&j>0)
	{
		if(s[i-1]==t[j-1])
		{
			x+=s[i-1];i--;j--;
		}
		else if(lcs[i-1][j]>lcs[i][j-1])i--;
		else j--;
	}
	reverse(all(x));
	cout<<x<<endl;

}
return 0;
}










Measured memory_bytes: 35456
N = int(input())
S = input()
keys = [str(i) for i in range(1000)]
count = 0
for i in range(10):
    keys[i] = '00' + keys[i]
for i in range(10,100):
    keys[i] = '0' + keys[i]
for i in keys:
    temp1 = i
    temp2 = ''
    if temp1[0] in S:
        search = S.find(temp1[0])+1
        if search >= len(S):
            continue
        temp2 = S[search:]
        if temp1[1] in temp2:
            search = temp2.find(temp1[1])+1
            if search >= len(temp2):
                continue
            temp2 = temp2[search:]
            if temp1[2] in temp2:
                count += 1
print(count)       

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

const int MAX = 3010;
const int64_t MOD = 998244353;
int64_t dp[MAX][MAX];

int main(){
  int N, S;
  cin >> N >> S;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec[i];
  }
  int64_t ans = 0;
  for(int i=0; i<N; i++){
    dp[i+1][vec[i]] += i+1;
    if(vec[i] == S){
      ans += (i+1)*(N-i);
      ans %= MOD;
    }
    for(int j=0; j<MAX; j++){
      dp[i+1][j] += dp[i][j];
      dp[i+1][j] %= MOD;
      if(dp[i][j] != 0 && j + vec[i] < MAX){
        dp[i+1][j+vec[i]] += dp[i][j];
        dp[i+1][j] %= MOD;
        if(j + vec[i] == S){
          ans += dp[i][j]*(N-i);
          ans %= MOD;
        }
      }
    }
  }
  cout << ans << endl;
}
        

Measured memory_bytes: 74152
#include <bits/stdc++.h>
using namespace std;
#define Sq 708
const int N=5e5 + 5;
int n, dd[N], c[N];
#define pii pair<int, int>
#define F first
#define S second

pair <pii, int > q[N];
int cur, ans[N];

bool cmp(pair <pii, int > A, pair <pii, int > B) {
    if(A.F.F/Sq != B.F.F/Sq) return A.F.F < B.F.F;
    return (A.F.F/Sq & 1 ? A.F.S < B.F.S : A.F.S > B.F.S);
}

void update(int color, int sig) {
    if(sig == 1 && dd[color] == 0) ++cur;
    if(sig ==-1 && dd[color] == 1) --cur;
    dd[color] += sig;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(fopen(".inp", "r")) freopen(".inp", "r", stdin);
    int Q;
    cin >> n >> Q;
    for(int i=1 ; i<=n ; ++i)cin >> c[i];
    for(int i=1 ; i<=Q ; ++i) {
        cin >> q[i].F.F >> q[i].F.S;
        q[i].S = i;
    }
    sort(q+1, q+Q+1, cmp);
    int l=1, r=0;
    for(int i=1 ; i<=Q ; ++i) {
        int u = q[i].F.F;
        int v = q[i].F.S;
        int id = q[i].S;


        while(u < l) update(c[--l], 1);
        while(u > l) update(c[l++], -1);

        while(v < r) update(c[r--], -1);
        while(v > r) update(c[++r], 1);

        ans[id] = cur;
    }
    for(int i=1 ;i<=Q; ++i) cout << ans[i] << '\n';


    return 0;
}


Measured memory_bytes: 15476