akhauriyash/Code-Regression huggingface dataset:
//#define _GLIBCXX_DEBUG
//#include <atcoder/all>
#include <bits/stdc++.h>

#ifndef ATCODER_DSU_HPP
#define ATCODER_DSU_HPP 1

#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder

#endif  // ATCODER_DSU_HPP

using namespace std;
using namespace atcoder;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const ll MOD=1000000007;
//const ll MOD=998244353;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);
int dx[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
int dy[9] = {0, 1, 0, -1, 1, -1, -1, 1, 0};

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



int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // cout << fixed << setprecision(15);

  ll N,M; cin>>N>>M;
  vector<ll> P(N); rep(i,N) cin>>P[i];
  dsu uf(N);
  rep(i,M){
    ll x,y; cin>>x>>y; x--; y--;
    uf.merge(x,y);
  }
  
  ll ans=0;
  rep(i,N){
    ll p=P[i]; p--;
    if(uf.same(p,i)) ans++;
  }
  
  cout<<ans<<'\n';
  
  return 0;
}


Measured memory_bytes: 4532
#include <iostream>
using namespace std;
int main(){
    int n;
    string s;
    cin >> n;
    cin >> s;
    long long cnt_r = 0, cnt_g = 0, cnt_b = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'R') cnt_r++;
        else if(s[i] == 'G') cnt_g++;
        else cnt_b++;
    }
    // 条件を満たさないもののカウント
    long long non_cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            int k = 2 * j - i;
            if(k < n){
                if(s[i] != s[j] && s[j] != s[k] && s[k] != s[i]) non_cnt++;
            }
        }
    }
    cout << cnt_r * cnt_g * cnt_b - non_cnt;
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  string s;
  ll k;
  cin >> s;
  cin >> k;
  ll n = s.length();
  bool same = true;
  vector<ll> v;
  ll c = 1;
  FOR(i, 1, n) {
    if (s[i] == s[i - 1])
      c++;
    else if (c > 1) {
      v.push_back(c);
      same = false;
      c = 1;
    }
    if (i == n - 1 && c > 1)

      v.push_back(c);
  }

  if (n == 1) {
    cout << (k - 1LL) / 2 << endl;
    return 0;
  }

  if (v.empty()) {
    if (s[0] == s[n - 1]) {
      cout << k - 1LL << endl;
    } else {
      cout << 0 << endl;
    }
    return 0;
  }

  if (v.size() == 1) {
    if (same) {
      cout << (n * k) / 2 << endl;
      return 0;
    }
    if (s[0] == s[n - 1]) {
      cout << k - 1LL + ((v[0] * k) / 2) << endl;
    } else {
      cout << (v[0] * k) / 2 << endl;
    }
    return 0;
  }

  ll ans = 0;
  FOR(i, 1, v.size() - 1) { ans += (v[i] / 2) * k; }
  ans += v[0] / 2;
  ans += v[v.size() - 1] / 2;
  if (s[0] == s[n - 1]) {
    ll tmp = v[0] + v[v.size() - 1];
    ans += (tmp / 2) * (k - 1);
  } else {
    ans += (v[0] / 2) * (k - 1);
    ans += (v[v.size() - 1] / 2) * (k - 1);
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;

int main(void)
{
    string s;
    string t;

    cin >> s;
    cin >> t;

    for (int i = 1; i <= 101; i++)
    {
        if(s==t){
            cout << "Yes";
            return 0;
        }
        char c;
        c = s.back();
        s.pop_back();
        s.insert(s.begin(),c);
    }
    cout << "No";
    return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main(){
    int n, k;
    std::cin >> n >> k;

    std::vector<int> h(n);
    for(int i = 0; i < n; ++i){
        std::cin >> h.at(i);
    }

    std::sort(std::begin(h), std::end(h), std::greater<int>());
    int min = std::min(n, k);
    std::cout << std::accumulate(std::begin(h) + min, std::end(h), 0ll) << std::endl;

    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	int normal,compress;
};


int N,M;
int POW[15];
int min_num[16384];
Info info[14];


void func(){

	for(int i = 0; i < N; i++){
		scanf("%d %d",&info[i].normal,&info[i].compress);
	}

	min_num[0] = 0;
	for(int i = 1; i < POW[N]; i++)min_num[i] = BIG_NUM;

	int ROOM,count,index_table[N];
	int add,compress_size;

	for(int state = 0; state < POW[N]-1; state++){
		if(min_num[state] == BIG_NUM)continue;

		ROOM = M;
		count = 0;

		for(int loop = 0; loop < N; loop++){
			if(state & (1 << loop)){
				ROOM += (info[loop].normal-info[loop].compress);
			}else{
				index_table[count] = loop;
				count++;
			}
		}

		for(int i = 0; i < POW[count]; i++){
			compress_size = 0;
			add = 0;
			for(int loop = 0; loop < count; loop++){
				if(i & (1 << loop)){
					compress_size += info[index_table[loop]].compress;
					add += POW[index_table[loop]];
				}
				if(compress_size > ROOM)continue;
				min_num[state+add] = min(min_num[state+add],min_num[state]+1);
			}
		}
	}

	if(min_num[POW[N]-1] == BIG_NUM){
		printf("Impossible\n");
	}else{
		printf("%d\n",min_num[POW[N]-1]);
	}
}


int main(){

	for(int i = 0; i < 15; i++)POW[i] = pow(2,i);

	while(true){
		scanf("%d %d",&N,&M);
		if(N == 0 && M == 0)break;

		func();
	}

	return 0;
}

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

#define MAX_N 100
int n, m;
vector<int> E[MAX_N];
bool seen[MAX_N], done[MAX_N];

bool check(int v){
    if(seen[v]) return true;
    seen[v] = true;
    for(int i = 0; i < E[v].size(); i++)
        if(!done[E[v][i]] && check(E[v][i])) return true;
    seen[v] = false;
    done[v] = true;
    return false;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int s, t;
        cin >> s >> t;
        E[s].push_back(t);
    }
    fill(seen, seen + n, false);
    fill(done, done + n, false);
    for(int i = 0; i < n; i++)
        if(!done[i] && check(i)){
            cout << 1 << endl;
            return 0;
        }
    
    cout << 0 << endl;
    
    return 0;
}


Measured memory_bytes: 3156
t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())

if t1 * a1 + t2 * a2 == t1 * b1 + t2 * b2:
    print('infinity')
    exit()

if a1 < b1:
    a1, a2, b1, b2 = b1, b2, a1, a2
d1 = (a1-b1)*t1
d2 = (a2-b2)*t2
if d1 + d2 > 0:
    print(0)
    exit()
if d1 == d2:
    print('infinity')
    exit()

dd = abs(d1 + d2)
if d1 % dd == 0:
    print(d1 // dd*2)
else:
    print((d1+dd-1)//dd*2-1)


Measured memory_bytes: 38384
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	a := iSScan(n)
	m := max(a)
	c := 0
	for _, v := range a {
		if v == m {
			c++
		}
	}
	if c > 1 {
		for i := 0; i < n; i++ {
			fmt.Println(m)
		}
	} else {
		for _, v := range a {
			if v == m {
				x := 0
				for _, w := range a {
					if w != m {
						x = larger(w, x)
					}
				}
				fmt.Println(x)
			} else {
				fmt.Println(m)
			}
		}
	}
}


Measured memory_bytes: 6448
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <fstream>
#include <iomanip>

typedef long double ld;
typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

template<class T> T maximum(T head, T tail) { return std::max(head, tail); }
template<class H, class... T> H maximum(H head, T... tail) { return std::max(head, maximum(tail...)); }

template<class T> T minimum(T head, T tail) { return std::min(head, tail); }
template<class H, class... T> H minimum(H head, T... tail) { return std::min(head, minimum(tail...)); }

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  ll i = 0;
  for (auto x : v) {os << " [" << i++ << "]" << x; if (i % 10 == 0) os << std::endl;}
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::vector< std::pair<T, S> > vp)
{
  ll i = 0;
  for (auto p : vp) {os << " [" << i++ << "]" << p.first << " " << p.second; if (i % 10 == 0) os << std::endl;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

//  bool judge = (vc == "1479");
//  if (judge) print("Yes");
//  else print("No");

  std::string s;
  std::cin >> s;

  ll cnt = 0LL;
  for (auto c : s) {
    if (c == '1') cnt++;
  }
  print(cnt);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional>
#include <unistd.h>
using namespace std; 
using namespace std::chrono; 
using namespace __gnu_pbds;
//mp.reserve(1024);
//mp.max_load_factor(0.25);
typedef tree<int, null_type, less<int>, rb_tree_tag,  
                tree_order_statistics_node_update>  
        ordered_set;  
#define ll long long int 

void addEdge(vector<ll> adj[], ll u, ll v) 
{ 
   adj[u].push_back(v); 
   adj[v].push_back(u); 
} 
int main() 
{ 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll x;
	cin>>x;
	ll sum=0,final1=0;
	sum+=500*(x/500);
	final1+=1000*(x/500);
	x-=sum;
	x/=5;
	final1+=5*(x);
	sum+=5*(x);
	cout<<final1<<endl;
  return 0; 
} 


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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main(){
string S;
cin >> S;
int sum = 0;
for(int i = 0; i < S.size(); i++){ 
     if(S[i] == '+') sum++;
     if(S[i] == '-') sum--;
}

print(sum);
}

Measured memory_bytes: 256
#![allow(unused)]

use std::{cell, cmp, collections, convert, fmt, io, iter, ops, str};
use io::{Read, Write};

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_owned()
}

fn parse_vec<T: str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {

    let n = {
        let tmp = parse_vec::<i32>();
        (tmp[0])
    };

    let mut bag :Vec<(i32,i32)> = Vec::with_capacity(100001);

    for i in 0..n {
        let (left, right) = {
            let vec = parse_vec::<i32>();
            (vec[0], vec[1])
        };
        bag.push((left,right));
    }
    let ans = bag.iter().fold(0, |acc, &(left, right)| acc + right - left + 1);
    println!("{}", ans);
}



Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
struct edge {
  int to, cap, rev;
};

vector<vector<edge>> e;
vector<int> used;

int dfs(int v, int t, int f) {
  if(v == t) return f;
  used[v] = 1;
  for(int i = 0; i < e[v].size(); i++) {
    if(e[v][i].cap && !used[e[v][i].to]) {
      int d = dfs(e[v][i].to, t, min(f, e[v][i].cap));
      if(d) {
        e[v][i].cap -= d;
        e[e[v][i].to][e[v][i].rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int main() {
  int n;
  scanf("%d", &n);
  vector<pair<int, int>> r(n);
  e = vector<vector<edge>>(2 * n + 2, vector<edge>());
  for(int i = 1; i <= n; i++) {
    e[0].push_back(edge{i, 1, e[i].size()});
    e[i].push_back(edge{0, 0, e[0].size() - 1});
    e[n + i].push_back(edge{2 * n + 1, 1, e[2 * n + 1].size()});
    e[2 * n + 1].push_back(edge{n + i, 0, e[n + i].size() - 1});
  }
  for(int i = 0; i < n; i++) scanf("%d %d", &r[i].first, &r[i].second);
  for(int i = 0; i < n; i++) {
    int c, d;
    scanf("%d %d", &c, &d);
    for(int j = 0; j < n; j++) {
      if(r[j].first < c && r[j].second < d) {
        e[i + 1].push_back(edge{j + 1 + n, 1, e[j + 1 + n].size()});
        e[j + 1 + n].push_back(edge{i + 1, 0, e[i + 1].size() - 1});
      }
    }
  }
  used = vector<int>(2 * n + 2, 0);
  int flow = 0, f;
  do {
    fill(used.begin(), used.end(), 0);
    f = dfs(0, 2 * n + 1, INT_MAX);
    flow += f;
  } while(f);
  printf("%d\n", flow);
}

Measured memory_bytes: 384
S = list(input())

ans = []
l = -1

for i in S:
    if i == '0':
        ans.append(i)
        l+=1
    elif i == '1':
        ans.append(i)
        l+=1
    else:
        if l>=0:
            del ans[l]
            l-=1
            
print(''.join(ans))

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
    int m,A,year,n,type,tesuryo,a,b,max;
    double riritsu;
    cin>>m;
    for(int j=0;j<m;j++){
        cin>>A>>year>>n;
        max=0;
        for(int i=0;i<n;i++){
            cin>>type>>riritsu>>tesuryo;
            a=A;
            b=0;
            if(type==0){
                for(int k=0;k<year;k++){
                    b+=a*riritsu;
                    a-=tesuryo;
                }
                a+=b;
            }else{
                for(int k=0;k<year;k++){
                    a+=a*riritsu;
                    a-=tesuryo;
                }
            }
            if(max<a){
                max=a;   
            }
        }
        cout<<max<<endl;
    }
    return 0;
}

Measured memory_bytes: 1232
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
struct Combination{
private:
    ll N;
    vector<ll> fac, facinv;

public:
    Combination(ll n){
        N = n;
        fac.push_back(1); fac.push_back(1);
        rep(i,2,N+1) fac.push_back(fac[i-1] * i % MOD);
        rep(i,0,N+1) facinv.push_back(power(fac[i], MOD-2));
    }
    ll power(ll x, ll n){
        if(n == 0) return 1LL;
        ll res = power(x * x % MOD, n/2);
        if(n % 2 == 1) res = res * x % MOD;
        return res;
    }
    ll nck(ll n, ll k){
        if(k == 0 || n == k) return 1LL;
        return fac[n] * facinv[k] % MOD * facinv[n-k] % MOD;
    }
    ll npk(ll n, ll k){
        if(k == 0 || n == k) return 1LL;
        return fac[n] * facinv[n-k] % MOD;
    }
    ll get(ll x){return fac[x];};
    ll getinv(ll x){return facinv[x];};
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,A,B,C;
    cin >> N >> A >> B >> C;
    Combination cb(200010);
    ll ans = 0;
    rep(M,N,2*N){
        ll res = 100 * M * cb.power(100-C, MOD-2) % MOD;
        ll p = cb.nck(M-1,N-1) * cb.power(A,N) % MOD * cb.power(B, M-N) % MOD * cb.power(A+B, MOD-1-M) % MOD;
        p += cb.nck(M-1,N-1) * cb.power(B,N) % MOD * cb.power(A, M-N) % MOD * cb.power(A+B, MOD-1-M) % MOD;
        p %= MOD;
        res *= p;
        res %= MOD;
        (ans += res) %= MOD;
    }
    print(ans);



}

Measured memory_bytes: 4848
from collections import deque

s1 = deque()
s2 = deque()

s = input()
totalarea = 0

for i,c in enumerate(s):
    if c == '\\':
        s1.append(i)
    elif s1 and c == '/':
        j = s1.pop()
        area = i - j
        totalarea +=  area
        subarea = area
        while s2 and s2[-1][0] > j:
            subarea += s2[-1][1]
            s2.pop()
        s2.append((j, subarea))

print(totalarea)
print(len(s2), end='')
if s2:
    print(" ",end="")
    areas = [str(puddle[1]) for puddle in s2]
    print(" ".join(areas))
else:
    print("")



Measured memory_bytes: 6568
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		double answer = 0;

		for (int i = 0; i < N; i++) {
			double num = Double.valueOf(sc.next());
			String str = sc.next();
			if ("JPY".equals(str)) {
				answer += num;
			} else {
				answer += num * 380000;
			}
		}

		System.out.println(answer);
	}
}


Measured memory_bytes: 21844
#include<stdio.h>

int main(void){

	int x[6];


	for(int i = 0; i < 5; i++){
		scanf("%d", &x[i]);
	}


	for(int i = 1; i < 6; i++){
		if(x[i - 1] == 0)
			printf("%d", i);
	}

	return 0;

	}

Measured memory_bytes: 1672
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000000000000000
int main(){
	int n,m,i;cin>>n>>m;//n駒で全地点を訪れたい
	vector<int> x(m);
	vector<pair<int,int>> minus(m);
	minus[0]=make_pair(0,0);

	for(i=0;i<m;i++){
		cin>>x[i];
	}
	sort(x.begin(),x.end());


	for(i=1;i<m;i++){//2点間距離
		minus[i]=make_pair(x[i]-x[i-1],i);
	}
	sort(minus.begin(),minus.end(),greater<pair<int,int>>());
	

	if(n>=m){cout<<0<<endl;return 0;}

	i=1;
	while(i<n){
		minus[i-1].second=10000000;
		i++;
	}

	int ans=0;
	for(i=0;i<m;i++){
		if(minus[i].second!=10000000){
			ans+=(minus[i].first);
		}
	}

	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 1536
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	B
# CreatedDate:  2020-05-30 21:22:38 +0900
# LastModified: 2020-05-30 21:30:58 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd


def main():
    t = input()
    
    print(t.replace('?','D'))


if __name__ == "__main__":
    main()


Measured memory_bytes: 9504
fun main(args: Array<String>) {
    arc067a()
}

fun arc067a() {
    val n = readLine()!!.toLong()

    if (n == 1L) return println(1)

    val answer = (2..n).map { primeFactorization(it).toList() }.flatten()
        .groupBy { it.first }.map { entry -> entry.value.map { it.second }.sum() }
        .fold(1L) { acc, l -> mod(acc * (l + 1)) }

    println(answer)
}

private const val MOD = (1e9 + 7).toLong()
private fun mod(x: Long): Long = x % MOD

private fun primeFactorization(n: Long): Map<Long, Long> {
    val factors = mutableMapOf<Long, Long>()
    var temp = n
    var i = 2L
    while (i * i <= temp) {
        while (temp % i == 0L) {
            factors[i] = (factors[i] ?: 0) + 1
            temp /= i
        }
        i++
    }
    if (temp > 1) factors[temp] = 1
    return factors
}


Measured memory_bytes: 32096
//url:
//problem name:

#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long,long>;
using veci = vector<int>;
using vecl = vector<long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long,long>>;

ll gcd(ll a,ll b) {
    if(b == 0) return a;
    else return gcd(b,a%b);
}

int main() {
    ll K;
    cin >> K;
    ll ans = 0;
    for(ll a = 1; a <= K; a++)
        for(ll b = 1; b <= K; b++)
            for(ll c = 1; c <= K; c++) 
                ans += gcd(gcd(a,b),c);

    cout << ans << endl;
}


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

int main()
{
    int A , B , s , m ;
    cin >> A >> B ;
    s = fmax (A , B);
    m = fmin ( A , B);
    if((s-1) >= m)
    {
        cout << 2 * s - 1  << endl;
    }
    else
    {
        cout << s + m << endl;
    }

    return 0;
}


Measured memory_bytes: 3680
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int k=sc.nextInt();
    int s=sc.nextInt();
    int cnt=0;
    sc.close();
    for(int i=Math.max(0,s-2*k);i<=Math.min(k,s);i++){
      for(int j=Math.max(0,s-i-k);j<=Math.min(k,s-i);j++){
        if((s-i-j)>=0&&(s-i-j)<=k){
          cnt++;
        }
      }
    }
    System.out.println(cnt);
  }
}

Measured memory_bytes: 23892
h,w = map(int,input().split())
lst=[list(map(str, input())) for i in range(h)]

dxy = [(1,0),(0,1),(0,-1),(-1,0)]
flag = False

for y in range(h):
    for x in range(w):
        if lst[y][x] == ".":
            continue
        sum_count = len(dxy)
        dot_count = 0
        for dx,dy in dxy:
            if x+dx < 0 or x+dx > w-1 or y+dy < 0 or y+dy > h-1:
                sum_count -= 1
                continue
            if lst[y+dy][x+dx] == ".":
                dot_count += 1
        if sum_count == dot_count:
            flag = True
            break
    if flag:
        break

if flag:
    print("No")
else:
    print("Yes")


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

template <class T>
inline bool read(T &ret)
{
    char c;
    int sgn;
    if (c = getchar(), c == EOF)
    {
        return 0;
    }
    while (c != '-' && (c < '0' || c > '9'))
    {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}

template <class T>
inline void write(T x)
{
    if (x > 9)
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

const int MAXN=21;
int ans=0;
int a[MAXN],b[MAXN],c[MAXN];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=1;i<n;i++)
        cin>>c[i];
    a[0]=-1;
    for(int i=1;i<=n;i++)
    {
        ans+=b[a[i]];
        if(i!=1&&a[i]==a[i-1]+1)
            ans+=c[a[i-1]];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
S.append("")

cnt = 0

def search(S,n, key):
    S[n] = key
    j = 0
    while( S[j] != key):
        j += 1


    return j != n

for i in T:
    if(search(S,n,i)): cnt += 1

print(cnt)


Measured memory_bytes: 6552
#include <stdio.h>

int i,j;

int main(void)
{
    int X,E,ans=1,key=0;
    scanf("%d",&X);
    for(i=X;i>0;i--)
    {
        for(j=2;j<i;j++)
        {
            E=i;
            while(E%j==0)
            {
                E/=j;
            }
            if(E==1)
            {
                key=1;
                break;
            }
        }
        if(key==1)
        {
            ans=i;
            break;
        }
            
    }
    printf("%d",ans);
    
    return 0;
    
}


Measured memory_bytes: 128
import java.io.IOException;
import java.util.Scanner;

class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int n;
		while ((n = scan.nextInt()) != -1) {

			int p;
			if (n <= 10) {
				p = 1150;
			} else if (n <= 20) {
				p = 1150 + (n - 10) * 125;
			} else if (n <= 30) {
				p = 2400 + (n - 20) * 140;
			} else {
				p = 3800 + (n - 30) * 160;
			}

			System.out.println(4280 - p);

		}

	}
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) a[i] /= 400;
  sort(a, a + n);
  int f = a + n - lower_bound(a, a + n, 8);
  int res = 0;
  for (int i = 0; i < 8; i++) {
    res += binary_search(a, a + n, i);
  }
  if (!res) {
    res++;
    f--;
  }
  cout << res << " " << res + f << "\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,j) for (int (i)=0;(i)<(int)(j);++(i))
#define put(i) cout << i << endl
using namespace std;
const int MAX = 1000;

int n;
string s1, s2;
int dp[MAX+1][MAX+1];

int rec(int x, int y) {
    if (dp[y][x] >= 0) {
        return dp[y][x];
    }
    int sz1 = s1.size(), sz2 = s2.size();
    int ret;
    if (x == sz1 || y == sz2) {
        ret = 0;
    }
    else if (s1[x] == s2[y]) {
        ret = rec(x+1, y+1)+1;
    }
    else {
        ret = max(rec(x+1, y), rec(x, y+1));
    }
    return dp[y][x] = ret;
}

void solve() {
    while (n--) {
        memset(dp, -1, sizeof(dp));
        cin >> s1 >> s2;
        cout << rec(0, 0) << endl;
    }
}

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

Measured memory_bytes: 7204
s=input()
if 10*int(s[0])+int(s[1])<=12 and int(s[0])+int(s[1])!=0:
  if 10*int(s[2])+int(s[3])<=12 and int(s[2])+int(s[3])!=0:
    print("AMBIGUOUS")
  else:
    print("MMYY")
if 10*int(s[0])+int(s[1])>=13 or int(s[0])+int(s[1])==0:
  if 10*int(s[2])+int(s[3])<=12 and int(s[2])+int(s[3])!=0:
    print("YYMM")
  else:
    print("NA")

Measured memory_bytes: 3316
#include <iostream>

using namespace std;

int table[501][501];

int main() {
  int N, M, Q;
  cin >> N >> M >> Q;
  for (int i = 0; i < M; i++) {
    int l, r;
    cin >> l >> r;
    table[l][r]++;
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      table[i][j] += table[i - 1][j] + table[i][j - 1] - table[i - 1][j - 1];
    }
  }
  for (int i = 0; i < Q; i++) {
    int p, q;
    cin >> p >> q;
    const int ans =
        table[q][q] - table[q][p - 1] - table[p - 1][q] + table[p - 1][p - 1];
    cout << ans << endl;
  }
  return 0;
}


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

#define endl "\n"
#define INF (int) 9e18
#define HELL (int) (1e9 + 7)
#define int long long
#define double long double
#define uint unsigned long long
#define deb(x) cerr << #x << " => " << x << "\n"
#define deba(x) cerr << #x << "\n"; for (auto a : x) cerr << a << " "; cerr << "\n";
#define debm(x) cerr << #x << "\n"; for (auto a : x){for(auto b : a) cerr << b << " "; cerr << "\n";}
#define getMat(x, n, m, val) vector<vector<int>> x(n, vector<int> (m, val))
#define fastio ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define pout cout << fixed << setprecision(10)

int fastpow(int a, int b, int m) {
    int res = 1; a %= m; while (b > 0) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m; b >>= 1;
    } return res;
}

int now() {
    return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now()
    .time_since_epoch()).count();
}

int32_t main() { fastio;
    time_t start = now();

    int n, a, b;
    cin >> n >> a >> b;
    int x = n / (a + b);
    cout << x * a + min(a, n - x * (a + b)) << endl;

    cerr << "TIME => " << now() - start << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
#define int long long
using namespace std;
signed main() {
	int N, D;
	cin >> N >> D;

	vector<int>X(N*2);
	int A = 0;
	

	for (int i = 0; i < N*2; i++) {
		cin >> X[i];
	}
	for (int i = 0; i < N * 2; i+=2) {
		if (D >= sqrt(X[i] * X[i] + X[i + 1] * X[i + 1])) {
			A++;
		}
		
	}
	cout << A << endl;
}

Measured memory_bytes: 6428
import sys

import numpy as np

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

X, Y, Z, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))

AB = np.add.outer(A, B).flatten()
AB.sort()
C.sort()
ABC = np.add.outer(AB[-K:], C).flatten()
ABC.sort()

for i in range(K):
    print(ABC[len(ABC) - 1 - i])


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

public class Main
{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    while(true)
    {
      int n = sc.nextInt();
      if(n == 0)
      {
        break;
      }
      int[] scores = new int[n];
      int average = 0;
      for(int i = 0; i < n; i++)
      {
        scores[i] = sc.nextInt();
        average += scores[i];
      }
      Arrays.sort(scores);
      average = (average - scores[0] - scores[n - 1]) / (n - 2);
      System.out.println(average);
    } 
  }
}

Measured memory_bytes: 29232
fun main(args: Array<String>) {
    var n = readLine()!!.toInt()
    var s = readLine()!!.toString()
    var c = mutableMapOf<Char, Int>('R' to 0, 'G' to 0, 'B' to 0)
    for (i in s) {
        c[i] = c[i]!! + 1
    }
    var diff = 0
    var ans = 1L
    for (d in 1..((n-1)/2)){
        for (i in 0..(n-d-d-1)) {
            if (s[i] != s[i+d] && s[i+d] != s[i+d+d] && s[i+d+d] != s[i]) {
                diff += 1
            }
        }
    }
    for ((x, y) in c){ans *= y}
    println(ans-diff)
}


Measured memory_bytes: 37316
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod(ll n){return n%=MOD1;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{ ll a , b;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;}
int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;}
void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);}
void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);}

int main(void){
    // char ;
    ll n,ans=0;
    scanf("%lld",&n);
    ll a[n];
    rep(i,0,n){
        scanf("%lld",&a[i]);
    }
    sortup(a,n);
    ll r=1;
    rep(i,1,n){
        if(a[i]==a[i-1]){
            r++;
        }else{
            ans+=r%2;
            r=1;
        }
    }
    ans+=r%2;

    
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
const int MAXW = 10000;
int n, k, weight[MAXN];
int getloadedNum(int P)
{
	int num = 0;
	for (int i = 0; i < k; i++)
	{
		int temp = 0;
		while (temp + weight[num] <= P)
		{
			temp += weight[num];
			num++;
			if (num == n)
				return n;
		}
	}
	return num;
}
int solve()
{
	int left = 0;
	int right = MAXN * MAXW;
	while (left+1<right)
	{
		int mid = (left + right)/2;
		int maxNum = getloadedNum(mid);
		if (maxNum >= n)
			right = mid;
		else
			left = mid;
	}
	return right;
}
int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> weight[i];
	cout << solve() << endl;
}


Measured memory_bytes: 3456
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#define ll long long
using namespace std;
ll k[100004];
int main()
{
 	ll n;
 	ll m;
 	ll y=0;
	 ll ans=1e9;
 	scanf("%lld%lld",&n,&m);
	ll p=m;
 	for(ll i=1;i<=n;i++)
 	{
 		scanf("%lld",&k[i]);
	}
	sort(k+1,k+n+1);
	for(ll i=1;i<=n-m+1;i++)
	{
		ans=min(k[i+m-1]-k[i],ans);
		p=m+1;
	}
	printf("%lld\n",ans);
	return 0;
}
//int main()
//{
//    int n, k;
//    scanf("%d %d", &n, &k);
//    int h[100005];
//    for(int i = 1; i <=n; i++)
//        scanf("%d", &h[i]);
//    sort(h+1, h + n+1);
//    int ans = 1e9;
//    for(int i = 1; i <= n - k+1; i++)
//        ans = min(ans, h[i+k-1] - h[i]);
//    printf("%d\n", ans);
//    return 0;
//}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k,n,a,b,c,d,max_dis=0;
    cin>>k>>n;
    int i,x[n];
    for(i=0;i<n;i++)
    {
        cin>>x[i];
    }
    max_dis=x[n-1]-x[0];
    int min_dis=k;
    for(i=1;i<n;i++)
    {
        int dis=(k-x[i])+x[i-1];
        if(dis<min_dis) min_dis=dis;
    }
    a=min(max_dis,min_dis);
    cout<<a<<endl;
    return 0;
}


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

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int l = in.nextInt();
        String[] s = new String[n];
        for(int i=0; i<n; i++) {
            s[i] = in.next();
        }
        Arrays.sort(s);
        for(int i=0; i<n; i++) {
            System.out.print(s[i]);
        }
        System.out.println();

        in.close();
    }
}


Measured memory_bytes: 9812
import sys,bisect
input = sys.stdin.readline

x = int(input())
if x <= 599:
    print(8)
elif x <= 799:
    print(7)
elif x <= 999:
    print(6)
elif x <= 1199:
    print(5)
elif x <= 1399:
    print(4)
elif x <= 1599:
    print(3)
elif x <= 1799:
    print(2)
else:
    print(1)

Measured memory_bytes: 62064
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#define int long long
#define ll long long
#define mod  1000000007
#define MOD  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
#define ps push_back
#define all(x) x.begin(),x.end()
double pi = 3.141592653589793;
using namespace std;
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; }
//ここから始めよう
signed main(){
    vector<int> a;
    rep(i,0,6){
        int w;cin>>w;
        a.ps(w);
    }
    sort(all(a));
    int cnt=0;
    vector<int> v;
    rep(i,0,6){
        if(i==0||a[i]==a[i-1])cnt++;
        else {
            v.ps(cnt);cnt=1;
        }
    }
    if(cnt)v.ps(cnt);
    sort(all(v));
    if(v.size()!=4)cout<<"NO"<<endl;
    else if(v[0]==1&&v[1]==1&&v[2]!=1)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}



Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  if A[i]%2 == 0:
    if A[i]%3 == 0 or A[i]%5 == 0:
      continue
    else:
      print('DENIED')
      exit()
  else:
    continue
print('APPROVED')

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

class Mondai
{
    static void Main()
    {
        var nk = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var N = nk[0];
        var K = nk[1];
        var ans = K == 1 ? 0 : N - K;
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 13268
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;

int a[100005];
int gcd(int x, int y){
    return x%y?gcd(y,x%y):y;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    int mx = 0;
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
        mx = max(mx,a[i]);
    }
    int g = a[1];
    for(int i = 2 ; i <= n ; i++){
        g = gcd(g,a[i]);
    }
    if(mx>=k&&k%g==0) cout << "POSSIBLE";
    else cout << "IMPOSSIBLE";
}


Measured memory_bytes: 640
s = input()
n = len(s)
sum = 0
for i in range(2**(n-1)):
  k = i
  a = 0
  b = 0
  for j in range(n):
    b += 1
    if(k%2==1):
      sum += int(s[a:b])
      a = b
    elif(k==0):
      sum += int(s[a:n])
      break;
    k = k//2
print(sum)

Measured memory_bytes: 3064
a = [list(map(int,input().split())) for _ in range(3)]
n = int(input())
for i in range(n):
    b = int(input())
    for c in range(3):
        for r in range(3):
            if a[c][r] == b:
                a[c][r] = 0
R = [0,0,0]
C = [0,0,0]
S = [0,0]
for i in range(3):
    for j in range(3):
        R[i] += a[i][j]  # よこ
        C[j] += a[i][j]  # たて
for i in range(3):  # ななめ
    S[0] += a[i][i]
    S[1] += a[i][2-i]
print('Yes' if 0 in R + C + S else 'No')

Measured memory_bytes: 3064
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,item):
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
print(solve(R,C,K,item))


Measured memory_bytes: 177164
k, q = map(int, input().split())
d = list(map(int, input().split()))

def solve():
    n, x, m = map(int, input().split())
    ans = 0
    rn = (n - 1) % k
    f = x % m
    for i in range(k):
        if d[i] % m == 0:
            continue
        if i < rn:
            c = (n - 1) // k + 1
        else:
            c = (n - 1) // k
        ans += c
        f += c * (d[i] % m)
    ans -= f // m
    print(ans)

for _ in range(q):
    solve()

Measured memory_bytes: 48092
W, H, N = gets.chomp.split.map(&:to_i)
Ws = [0, W]
Hs = [0, H]  # どっちも右上

N.times do |i|
  xi, yi, ai = gets.chomp.split.map(&:to_i)
  # 題意から
  if ai == 1
    Ws[0] = [Ws[0], xi].max
  elsif ai == 2
    Ws[1] = [Ws[1], xi].min
  elsif ai == 3
    Hs[0] = [Hs[0], yi].max
  else
    Hs[1] = [Hs[1], yi].min
  end
end

puts [Ws[1] - Ws[0], 0].max * [Hs[1] - Hs[0], 0].max


Measured memory_bytes: 1788
import math
n=int(input())
dp=[[0]*3 for i in range(n+1)]
s=[]
for i in range(n):
    arr=list(map(int,input().split()))
    s.append(arr)

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            dp[i+1][j]=max(dp[i][k]+s[i][j],dp[i+1][j])
print(max(dp[n]))

Measured memory_bytes: 101608
import collections
n,k = list(map(int,input().split()))
d_list = []
a_list = []
for i in range(k):
    d = int(input())
    a = list(map(int,input().split()))
    d_list.append(d)
    a_list.extend(a)
cnt = 0
cnt_dict = collections.Counter(a_list)
for i in range(1,n+1):
    if cnt_dict[i] == 0:
        cnt += 1
print(cnt)

Measured memory_bytes: 9484
N = int(input())

if N % 2 == 0:
  print(N//2, N, N)
else:
  for i in range(1, N):
    if N < 4*i:
      n = 4*i - N
      break
  if n == 1:
    j, k = 2*N*i, 2*N*i
  else:
    if i % 3 == 0:
      j, k = 2*N*i//3, 2*N*i//3
    else:
      for x in range(100):
        flag = False
        for y in range(1, n//2+1):
          if ((N*i)%y==0) and ((N*i)%(n-y)==0):
            j = (N*i) // y
            k = (N*i) // (n-y)
            flag = True
            break
        if flag:
          break
        else:
          i += 1
          n += 4
  print(i, j, k)

Measured memory_bytes: 9200
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>

int main(){
  int N; cin >> N;
  int x[N], y[N]; rep(i,N) cin >> x[i] >> y[i];
  map<pair<ll,ll>,int> d;

  for (int i=0;i<N-1;i++){
    for (int j=i+1;j<N;j++){
      ll dx = x[i]-x[j], dy = y[i]-y[j];
      if (dx<0) dx = -dx, dy = -dy;
      if (dx==0) dy = abs(dy);
      d[make_pair(dx,dy)]++;
    }
  }
  int MAX = 0;
  for (auto p:d){
    MAX = max(MAX, p.second);
  }
  cout << N - MAX << endl;
  

  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin >> s;
    string from = ",";
    string to = " ";

    string::size_type pos = s.find(from);
    while(pos != string::npos){
        s.replace(pos, from.size(), to);
        pos = s.find(from, pos + to.size());
    }
    cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    int n;
    string s,t;
    cin>>n>>s>>t;
    rep(i,2*n){
        if(i%2==0) cout<<s[i/2];
        else cout<<t[i/2];
    }
}

Measured memory_bytes: 3600
from itertools import combinations
n, k = map(int, input().split())
dots = sorted([list(map(int, input().split())) for _ in range(n)])

ans = float("inf")
for x1, x2 in combinations(range(n), 2):
	wid = dots[x2][0] - dots[x1][0]
	dots_cand = sorted(dots[x1: x2 + 1], key=lambda x: x[1])
	for y1, y2 in combinations(range(x2 + 1 - x1), 2):
		if y2 - y1 + 1 >= k:
			area = (dots_cand[y2][1] - dots_cand[y1][1]) * wid
			if area < ans:
				ans = area

print(ans)

Measured memory_bytes: 42220
n = int(input())
l = input()
a = l.split(' ')

tmp = 0
tmp2 = 0

for i in range(n):
    tmp += int(a[i])

for i in range(n):
    tmp2 += int(a[i])*int(a[i])

print(int((tmp*tmp-tmp2)//2)%1000000007)

Measured memory_bytes: 81976
#include <stdio.h>
#include <string.h>

int main(void){
	int map[255];
	map['I'] = 1;
	map['V'] = 5;
	map['X'] = 10;
	map['L'] = 50;
	map['C'] = 100;
	map['D'] = 500;
	map['M'] = 1000;
	int sum = 0;
	char in[101];
	int len;

	while(scanf("%s", in) != EOF){
		len = strlen(in);
		int i = 0;
		sum = 0;
		for(i=0; i<len-1; ++i){
			if(map[in[i]] < map[in[i+1]]){
				sum += map[in[i+1]] - map[in[i]];
				i++;
			}else{
				sum += map[in[i]];
			}
		}
		if(i<len){ sum += map[in[i]]; }
		printf("%d\n", sum);
	}
	return 0;
}

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

int A, B, C, D;

long power(long base, long exponent){
    if(exponent % 2){
        return power(base, exponent - 1) * base % long(1e9 + 7);
    }else if(exponent){
        long root_num = power(base, exponent / 2);
        return root_num * root_num % long(1e9 + 7);
    }else{
        return 1;
    }
}

long factorial_surplus[10000];

long combination(int n, int r){
    return factorial_surplus[n] * power(factorial_surplus[r] * factorial_surplus[n - r] % long(1e9 + 7), 1e9 + 5) % long(1e9 + 7);
}

long dp[1001][1001];

long make_group(int member, int remaining){
    if(!remaining){
        return 1;
    }else if(member == B + 1){
        return 0;
    }else if(dp[member - A][remaining - 1] != -1){
        return dp[member - A][remaining - 1];
    }else{
        long ans = make_group(member + 1, remaining);
        long combination_num = 1;
        for(int i = 1; i < C && remaining >= member * i; i++){
            combination_num *= combination(remaining - member * (i - 1), member);
            combination_num %= long(1e9 + 7);
            combination_num *= power(i, long(1e9 + 5));
            combination_num %= long(1e9 + 7);
        }
        for(int i = C; i <= D && remaining >= member * i; i++){
            combination_num *= combination(remaining - member * (i - 1), member);
            combination_num %= long(1e9 + 7);
            combination_num *= power(i, long(1e9 + 5));
            combination_num %= long(1e9 + 7);
            ans += make_group(member + 1, remaining - member * i) * combination_num;
            ans %= long(1e9 + 7);
        }
        return dp[member - A][remaining - 1] = ans;
    }
}

int main(){
    int N;
    cin >> N >> A >> B >> C >> D;
    long times_num = 1;
    for(long i = 0; i < 10000; i++){
        factorial_surplus[i] = times_num;
        times_num *= i + 1;
        times_num %= long(1e9 + 7);
    }
    for(int i = 0; i <= 1000; i++){
        for(int j = 0; j <= 1000; j++){
            dp[i][j] = -1;
        }
    }
    cout << make_group(A, N) << endl;
}


Measured memory_bytes: 8192
n=int(input())
s=input()
answer=""
alphabet=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for i in range(len(s)):
    answer+=alphabet[alphabet.index(s[i])+n]
print(answer)

Measured memory_bytes: 3064