akhauriyash/Code-Regression huggingface dataset:
def solve(n, k, r, s, p, t):
    res = 0
    u_list = [""] * n
    for i in range(k):
        if t[i] == "r":
            u_list[i] = "p"
            res += p
        elif t[i] == "s":
            u_list[i] = "r"
            res += r
        else:
            u_list[i] = "s"
            res += s

    for i in range(k, n):
        if t[i] == "r":
            if u_list[i - k] != "p":
                u_list[i] = "p"
                res += p
            else:
                u_list[i] = "x"
        elif t[i] == "s":
            if u_list[i - k] != "r":
                u_list[i] = "r"
                res += r
            else:
                u_list[i] = "x"
        else:
            if u_list[i - k] != "s":
                u_list[i] = "s"
                res += s
            else:
                u_list[i] = "x"
    return res


def main():
    n, k = map(int, input().split())
    r, s, p = map(int, input().split())
    t = input()
    res = solve(n, k, r, s, p, t)
    print(res)


def test():
    assert solve(5, 2, 8, 7, 6, "rsrpr") == 27
    assert solve(7, 1, 100, 10, 1, "ssssppr") == 211
    assert solve(30, 5, 325, 234, 123, "rspsspspsrpspsppprpsprpssprpsr") == 4996


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 4084
#include<iostream>
#include<string>
#include<map>
#include<set>
using namespace std;

int main() {
  string S, T;
  cin >> S >> T;

  map<char, set<char>> mp1, mp2;
  for (int i=0 ; i<S.size() ; i++) {
    mp1[S[i]].insert(T[i]);
    mp2[T[i]].insert(S[i]);
  }
  for (auto itr = mp1.begin() ; itr != mp1.end() ; ++itr) {
    pair<char, set<char>> st = *itr;
    if (st.second.size() > 1) {
      printf("No\n");
      return 0;
    }
  }
  for (auto itr = mp2.begin() ; itr != mp2.end() ; ++itr) {
    pair<char, set<char>> st = *itr;
    if (st.second.size() > 1) {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");

}


Measured memory_bytes: 776
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i=a;i<b;i++)
#define REP(i, n) FOR(i, 0, n)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
typedef vector<int> vi;
#define PB push_back
#define MP make_pair

int n;
#define N 112345
int a[N];
vi p;

int main(){
	scanf("%d", &n);
	REP(i, n) scanf("%d", a+i);
	int x=0;
	REP(i, n) LAR(x, a[i]);
	FOR(i, 1, x+1) if(x%i==0) p.PB(i);
	int ans=0;
    
	REP(i, n){
		REP(j, p.size()){
			int k=p[j];
			if(a[i]<=k){
				ans+=k-a[i];
				break;
			}
		}
	}
	printf("%d\n", ans);
}

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

int main () {
  int n; cin >> n;
  set<string> ans;
  for (int i = 0; i < n; ++i) {
    string s; cin >> s; ans.insert(s);
  }
  cout << ans.size() << endl;
  return 0;
}

Measured memory_bytes: 19224
n, q = map(int, input().split())
s = input()


t = [0] * (n+1)
for i in range(n):
    if s[i:i+2] == 'AC':
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]

        
for i in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])


Measured memory_bytes: 6188
n, m, c = list(map(int, input().split()))
B = list(map(int, input().split()))
count = 0
li = [list(map(int, input().split())) for i in range(n)]

for i in range(n):
    d = 0
    for j in range(m):
        d += li[i][j] * B[j]
    else:
        d += c
        if d > 0:
            count += 1
print(count)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    
    try( BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      String result = "No";
      String inStr  = br.readLine();
      String target = br.readLine();
      String ring = inStr + inStr;

      if( inStr.length() >= target.length())
        for(int i = 0; i < inStr.length(); i++) {
          if( target.charAt(0) == ring.charAt(i) ){
            if(target.equals(ring.substring(i, i+target.length()))) {
              result = "Yes";
              break;
            }
          }
        }

      System.out.println(result);
    }
  }
}


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

#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define all(v) v.begin(), v.end()
#define ar array

#define F first
#define S second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pll = pair <ll, ll>;
using ld = long double;

// const int mod = 1e9 + 7;
const int mod = 998244353;
const ll inf = 2e9;
const ll INF = 2e18;
const ld EPS = 1e-7;

const int N = 1e6 + 5;

int pref[N], suff[N];

int a[N];

void solve () {
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; ++ i) {
		cin >> a[i];
		pref[i] = __gcd (pref[i - 1], a[i]);
	}
	int best = 0;
	for (int i = n ; i >= 1 ; -- i) {
		suff[i] = __gcd (suff[i + 1], a[i]);
		best = max (best, __gcd (pref[i - 1], suff[i + 1]));
	}
	cout << best;
}

int main () {
	ios;
	int tt = 1;
	// cin >> tt;
	while (tt--) {
		solve();
		cout << "\n";
	}
}

Measured memory_bytes: 8832
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
vi stc[1010];
int idx[1010];
int A[1010];

void solve() {
	cin >> N;
	rep(i, 0, N) {
		rep(j, 0, N - 1) {
			cin >> A[j]; A[j]--;
		}
		rer(j, N - 1, 0) stc[i].pb(A[j]);
	}
	int cnt = 0;
	queue<int> que;
	rep(i, 0, N) que.push(i);
	while(true) {
		int n = sz(que);
		set<int> tmp;
		while(n--) {
			int v = que.front();
			que.pop();
			if(stc[v].empty()) continue;
			int u = stc[v].back();
			if(!stc[u].empty() && stc[u].back() == v) {
				tmp.insert(v);
				tmp.insert(u);
			}
		}
		if(tmp.empty()) break;
		// debug(vi(all(tmp)));
		for(auto idx: tmp) {
			stc[idx].pop_back();
			que.push(idx);
		}
		// rep(i, 0, N) {
		// 	debug(stc[i]);
		// }
		cnt++;
	}
	rep(i, 0, N) {
		if(!stc[i].empty()) {
			cout << -1 << "\n";
			return;
		}
	}
	cout << cnt << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 4352
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <climits>
using namespace std;

//===
template<typename Monoid, typename OP = function<Monoid(Monoid, Monoid)> >
struct SegmentTree {
    //    using OP = function<Monoid(Monoid, Monoid)>;
    
    vector<Monoid> tree;
    int size;
    const OP merge_monoid; // bin' operation
    const Monoid e; // neutral element
                                           
    SegmentTree(const Monoid &e, const OP &f):
        merge_monoid(f), e(e) {};
    void init(int nmemb) {
        size = nmemb;
        tree.assign(size << 1, e);
    };

    template<class InputIterator>
    SegmentTree(InputIterator first, InputIterator last,
                const Monoid &e, const OP &f):
        size(distance(first, last)), merge_monoid(f), e(e)
    {
        tree.resize(size << 1);
        int i;

        i = size;
        for (InputIterator itr = first; itr != last; itr++) {
            tree[i++] = *itr;
        }

        for (i = size - 1; i > 0; i--) {
            tree[i] = merge_monoid(tree[(i << 1)], tree[(i << 1) | 1]);
        }
    };

    inline void update(int k, Monoid dat) {
        k += size;
        tree[k] = dat;
        
        while(k > 1) {
            k >>= 1;
            tree[k] = merge_monoid(tree[(k << 1)], tree[(k << 1) | 1]);
        }
    };

    // [l, r)
    inline Monoid fold(int l, int r) {
        l += size; //points leaf
        r += size;

        Monoid lv = e;
        Monoid rv = e;
        while (l < r) {
            if (l & 1) lv = merge_monoid(lv, tree[l++]);
            if (r & 1) rv = merge_monoid(tree[--r], rv);

            l >>= 1;
            r >>= 1;
        }

        return merge_monoid(lv, rv);
    };

    inline Monoid operator[] (const int k) const {
        return tree[k + size];
    };
};
//===

//verify AOJ DSL_2_B
int AOJ_DSL2B() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    int com, x, y;
    SegmentTree<int> RSQ(0, [](int l, int r){return l + r;});

    scanf("%d %d", &n, &q);
    RSQ.init(n);

    while (q--) {
        scanf("%d %d %d", &com, &x, &y);
        x--;

        if (com == 0) {
            y += RSQ.fold(x, x + 1);
            RSQ.update(x, y);
        }
        else {
            printf("%d\n", RSQ.fold(x, y));
        }
    }

    return 0;
}

//verify AOJ DSL_2_A
int AOJ_DSL2A() {
    int n, q;
    int com, x, y;
    SegmentTree<int> RMQ((1u << 31u) - 1,
                         [](int l, int r){return min(l, r);});

    cin >> n >> q;
    RMQ.init(n);
    
    for (int i = 0; i < q; i++) {
        cin >> com >> x >> y;

        if (com == 0) {
            RMQ.update(x, y);
        }
        else {
            cout << RMQ.fold(x, y + 1) << endl;
        }
    }

    return 0;
}

int main() {
    //return AOJ_DSL2B();
    return AOJ_DSL2A();
}



Measured memory_bytes: 3640
s = input()
t = input()

s_list = sorted(s)
t_list = sorted(t, reverse=True)

s_str = ""
t_str = ""
for c in s_list:
	s_str += c
for c in t_list:
	t_str += c

if s_str < t_str:
	print("Yes")
else:
	print("No")

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>

int main()
{
	std::vector<int> A(9);
	std::map<int ,int> memo;
	for (int i = 0; i < 9; ++i) {
		std::cin >> A[i];
		memo[A[i]] = false;
	}

	int N;
	std::cin >> N;

	for (int i = 0; i < N; ++i) {
		int b;
		std::cin >> b;
		memo[b] = true;
	}


	for (int i = 0; i < 3; ++i) {
		if (memo[A[i * 3]] && memo[A[i * 3 + 1]] && memo[A[i * 3 + 2]]) {
			std::cout << "Yes" << std::endl;
			return 0;
		}

		if (memo[A[i]] && memo[A[i + 3]] && memo[A[i + 6]]) {
			std::cout << "Yes" << std::endl;
			return 0;
		}
	}

	if (memo[A[0]] && memo[A[4]] && memo[A[8]]) {
		std::cout << "Yes" << std::endl;
		return 0;
	}

	if (memo[A[2]] && memo[A[4]] && memo[A[6]]) {
		std::cout << "Yes" << std::endl;
		return 0;
	}



	std::cout << "No" << std::endl;
	return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

string t[4] = {"dream", "dreamer", "erase", "eraser"};
char s[100005];
bool dp[100005];
int check(int i, int j){
    bool ok = 1;
    for(int k=0;k<t[j].length();k++){
        if(s[i+k] == t[j][k]) continue;
        ok = 0;
        break;
    }
    return ok;
}

int main(){
    scanf("%s", s+1);
    int n = strlen(s+1);
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        if(dp[i-1]){
            if(i+4 <= n){
                if(check(i, 0)) dp[i+4] = 1;
                if(check(i, 2)) dp[i+4] = 1;
            }
            if(i+5 <= n){
                if(check(i, 3)) dp[i+5] = 1;
            }
            if(i+6 <= n){
                if(check(i, 1)) dp[i+6] = 1;
            }
        }
    }
    if(dp[n]) printf("YES\n");
    else printf("NO\n");
}

Measured memory_bytes: 3852
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

bool solve(){
  int n;
  int dp[SIZE] = {};
  vector<pair<int,int> > vec;
  
  scanf("%d",&n);

  if(n == 0) return false;


  for(int i=0;i<n;i++){
    int sh,sm,ss,eh,em,es;
    int s,e;

    scanf("%d:%d:%d %d:%d:%d",&sh,&sm,&ss,&eh,&em,&es);

    s = sh*3600 + sm*60 + ss;
    e = eh*3600 + em*60 + es;

    dp[s]++;
    dp[e]--;
    
  }

  int ans = 0;
  
  for(int i=0;i<24*60*60;i++){
    dp[i+1]+= dp[i];
    ans = max(ans, dp[i]);
  }

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

  return true;
}


int main(){

  while(solve());
  
  return 0;
}

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

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

using namespace std;

int main(){
  int N;
  while( cin >> N, N ){
    string s;
    cin >> s;
    vector<int> cards(N+1,0);
    int cur = 0;
    rep(i,(int)s.size()) {
      if( s[i] == 'M' ) ++cards[cur];
      else if( s[i] == 'S' ) { cards[N] += ( 1 + cards[cur] ); cards[cur] = 0; }
      else { cards[cur] += ( 1 + cards[N] ); cards[N] = 0; }
      ( cur += 1 ) %= N;
    }
    sort(cards.begin(),cards.begin()+N);
    rep(i,N+1) {
      if( i ) printf(" ");
      cout << cards[i];
    } puts("");
  }
  return 0;
}

Measured memory_bytes: 1232
N, D = gets.chomp.split.map(&:to_i)
X, Y = [], []
N.times{
  x, y = gets.chomp.split.map(&:to_i)
  X.push x
  Y.push y
}

puts X.zip(Y).map{ |x, y| Math.sqrt(x **2 + y ** 2) }.select{ |d| d <= D }.size


Measured memory_bytes: 30932
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF 1000000007 //1000000000000000003
#define MOD 1000000007
#define MAX 2000005

#define ll long long

//printf("%.10f", );
//cout << fixed << setprecision(10) << heikin << endl;
//vector<vector<int>> data(3, vector<int>(4, -1));
//left + 1 < top

using namespace std;
using P = pair<int, int>;
using Pc = pair<double, int>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };
const double PI = 3.141592653589793;
long long fact[MAX], inv[MAX];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

//////////////////////////////////

vector<vector<int>> tree(100005);
int color[100005];
map<P, int>colorMap;
int m = 0;

struct BridgeInfo {
	int town1;
	int town2;
	int year;
	BridgeInfo(int t1, int t2, int y) {
		town1 = t1;
		town2 = t2;
		year = y;
	}
};

struct People {
	int index;
	int town;
	int year;
	People(int i, int t, int y) {
		index = i;
		town = t;
		year = y;
	}
};

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

struct UnionFind {
	vector<int>uf;
	
	UnionFind(int size) :uf(size, -1) {};

	int root(int target) {
		if (uf[target] < 0)return target;
		else return uf[target] = root(uf[target]);
	}

	void merge(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (uf[b] < uf[a])swap(a, b);
		uf[a] += uf[b];
		uf[b] = a;
	}
};

ll CalcPow(ll num, ll power) {
	if (power == 0)return 1;
	if (power % 2 == 0) {
		ll half = CalcPow(num, power / 2);
		return (half * half) % MOD;
	}
	else return (num * CalcPow(num, power - 1)) % MOD;
}

ll combination(ll all, ll select) {
	if (all < select) return 0;
	if (all < 0 || select < 0) return 0;
	return fact[all] * (inv[select] * inv[all - select] % MOD) % MOD;
}

void initCombination(int max) {
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= max; ++i) {
		fact[i] = fact[i-1] * i % MOD;
	}

	inv[max] = CalcPow(fact[max], MOD - 2);
	for (int i = max - 1; 0 <= i; --i) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}

void dfs(int from) {
	int c = 1;
	for (auto t : tree[from]) {
		c = c != color[from] ? c : c + 1;
		color[t] = c;
		colorMap[make_pair(from, t)] = c;
		m = max(c, m);
		dfs(t);
		c++;
	}
}

int dp[105][4][2];

int main() {
	string S;
	cin >> S;
	int N = S.size();
	int K;
	cin >> K;
	vector<int>n(N);
	for (int i = 0; i < N;++i) {
		n[i] = (int)S[i] - 48;
	}

	dp[0][0][0] = 1;
	for (int i = 0; i < N;++i) {
		for (int j = 0; j <= K; ++j) {
			for (int k = 0; k < 2; ++k) {
				int target = n[i];
				for (int d = 0; d < 10; ++d) {
					int ni = i + 1; int nj = j; int nk = k;
					if (d != 0) nj++;
					if (K < nj) continue;
					if (ni < nj)continue;
					if (nk == 0) {
						if (target < d)continue;
						if (d < target)nk = 1;
					}
					dp[ni][nj][nk] += dp[i][j][k];
				}
			}
		}
	}
	
	int ans = dp[N][K][0] + dp[N][K][1];
	cout  << ans << endl;
}



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

int v,e;
set<pair<int,pair<int,int>>> g;

int a[10005]={};

void init(){
  for(int i=0;i<10005;i++)a[i]=i;
}

int find(int x){
  if(a[x]==x)return x;
  else return (a[x]=find(a[x]));
}

void un(int x,int y){
  a[find(x)]=y;
}

int main() {
  long long c=0;
  init();
  cin>>v>>e;
  for(int i=0;i<e;i++){
    int a,b,l;cin>>a>>b>>l;
    g.insert({l,{a,b}});
  }
  for(auto p:g){
    if(find(p.second.first)!=find(p.second.second)){
      c+=p.first;
      un(p.second.first,p.second.second);
    }
  }
  cout<<c<<endl;
}

Measured memory_bytes: 9396
const [_n, ..._edges] = require('fs')
  .readFileSync('/dev/stdin', 'utf8')
  .split(/\n/)
const n = Number(_n)

let result = (n * (n + 1) * (n + 2)) / 6

for (const _edge of _edges) {
  if (!_edge) {
    continue
  }
  let [u, v] = _edge.split(/ /).map(Number)
  if (u > v) {
    [u, v] = [v, u]
  }
  result -= u * (n - v + 1)
}
console.log(result)


Measured memory_bytes: 66632
import queue

k = int(input())

q = queue.Queue()
for i in range(1, 10):
  q.put(i)
for i in range(k-1):
  a = q.get()
  b = a % 10  #aの一の位
  if b != 0:
    q.put(10*a + b - 1)
  q.put(10*a + b)
  if b != 9:
    q.put(10*a + b + 1)

print(q.get())

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

using namespace std;

typedef long long	ll;

int main (){
	ll n, m;
	
	cin >> n >> m;
	if(n == 1LL && m == 1LL){
		cout << "1\n";
	}
	else if(n == 2LL || m == 2LL){
		cout << "0\n";
	}else if(n == 1){
		cout << m - 2LL << '\n';
	}else if(m == 1){
		cout << n - 2LL << '\n';
	}else{
		cout << (n - 2LL) * (m - 2LL) << '\n';
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long int
#define pb push_back
#define mod 1000000007
#pragma GCC optimize ("-O3")
#define mod2 998244353
#define MAXN 1000000000
#define v32 vector<int>
#define v64 vector<lli>
#define v1024 vector <vector <int>>
#define v4096 vector <vector <lli>>
#define vt vector
#define f(x, y, z) for (lli x = y; x < z; x++)
#define fd(x, y, z) for (lli x = y; x > z; x--)
#define lb lower_bound
#define ld long double
#define m64 map<lli,lli>
#define m32 map<int,int>
#define m64it map<lli,lli>::iterator
#define m32it map<int,int>::iterator
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ist insert
#define endl "\n"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define p_q priority_queue 
#define min_p_q priority_queue <int,vt <int>,greater <int>>
using namespace std;
using namespace __gnu_pbds; 
template <typename T> 
void DEBUG_ARR(vt<T> a,char c)
{
	f(i,0,a.size())cout<<a[i]<<c;
	cout<<"\n";
}

lli tmod(lli x,lli m){return (x%m+m)%m;}//USE AT YOUR OWN RISK
lli power(lli x, lli y) 
{
    lli res = 1;  
   
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x)%mod; 
        y = y>>1; 
        x = (x*x)%mod;  
    }
    if(res<0)
       res+=mod; 
    return res; 
}

int main() 
{ 
    fastio;
    string s,t;
    cin>>s>>t;
    int a,b;cin>>a>>b;
    string u;
    cin>>u;
    if(u==s)a--;
    else b--;
    cout<<a<<" "<<b<<"\n";
    return 0; 	
}


Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let k = read::<usize>();
    let s = read::<String>();
    if s.len() <= k {
        println!("{}", s);
    } else {
        let s = s.chars().collect::<Vec<_>>();
        for i in 0..k {
            print!("{}", s[i]);
        }
        println!("...",);
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

int main(){
	int N,A,J=0,K=0;
	cin >>N>>A;
	while(A%2==0){
		A/=2;
		K++;
	}
	for(int i=1;i<N;i++ ){
		cin >>A;
		while(A%2==0){
			A/=2;
			J++;
		}
		if(J<K)
			K=J;
      J=0;
	}
	cout << K << endl;
}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n,m;cin>>n>>m;
    vector<int> arr[n];
    int a,b;
    for (int i=0;i<m;i++){
        cin>>a>>b;
        arr[a-1].emplace_back(b);
        arr[b-1].emplace_back(a);
    }for (int i:arr[0]){
        for (int j:arr[i-1]){
            if (j==n){
                cout<<"POSSIBLE";
                return 0;
            }
        }
    }cout<<"IMPOSSIBLE";
    return 0;
}

Measured memory_bytes: 12016
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char a[23];
	bool f=0;
	for(int i=1;i<=3;i++) cin>>a[i];
		if((a[1]=='o')&&(a[2]=='o')&&(a[3]=='o'))
		{
		cout<<1000<<endl;
		f=1;
		} 
		else if((a[1]=='x')&&(a[2]=='x')&&(a[3]=='x')) 
		{
			f=1;
			cout<<700<<endl;
		}
		else if((a[1]=='x')&&(a[2]=='x')&&(a[3]=='o'))
		{
			f=1;
			cout<<800<<endl;
		}
		else if((a[1]=='x')&&(a[2]=='o')&&(a[3]=='x'))
		{
			f=1;
			cout<<800<<endl;
		}
		else if((a[1]=='o')&&(a[2]=='x')&&(a[3]=='x'))
		{
			f=1;
			cout<<800<<endl;
		}
		if(f==0) cout<<900<<endl;
	return 0;
} 

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

using namespace std;

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

    vector<long> B(N);

    int a;

    for(int i=0; i<N; i++){
        cin >> a;
        if(i == 0) B[i] = a;
        else B[i] = B[i-1] + a;
    }
    
    long sum = B[N-1];

    auto bp = upper_bound(B.begin(), B.end(), sum/2);
    long cand1 = *bp;
    long cand2 = *(--bp);
    long ans = min(abs(sum - 2 * cand1), sum - 2 * cand2);

    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 1792
/// Rustで競技プログラミングの入力をスッキリ記述するマクロ
///
/// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: usize,
        m: usize,
        ab_a: [[u64; 2]; m],
    }

    use std::collections::HashMap;
    use std::collections::HashSet;

    let mut movable = HashMap::new();
    for ab in &ab_a {
        let a = ab[0];
        let b = ab[1];

        movable.entry(a).or_insert(HashSet::new()).insert(b);
        movable.entry(b).or_insert(HashSet::new()).insert(a);
    }

    fn dfs(n: usize, state: u64, movable: &HashMap<u64, HashSet<u64>>, moved: Vec<u64>) -> u64 {
        if moved.len() + 1 == n {
            return 1;
        }

        let mut ans = 0;

        if let Some(tos) = movable.get(&state) {
            for to in tos {
                if !moved.contains(to) {
                    let mut moved = moved.clone();
                    moved.push(state);
                    ans += dfs(n, *to, movable, moved);
                }
            }
        }

        ans
    }

    println!("{}", dfs(n, 1, &movable, Vec::new()));
}


Measured memory_bytes: 4352
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

s = input()
n = len(s)
ans = [0] * n

base = 0
while True:
    firstL = s.find("L", base)
    ans[firstL] += (firstL-base)//2 + 1
    ans[firstL-1] += (firstL-base-1)//2 + 1

    nextR = s.find("R", firstL+1)
    end = False
    if nextR == -1:
        nextR = n
        end = True
    ans[firstL] += (nextR - firstL - 1) // 2
    ans[firstL-1] += (nextR - firstL) // 2

    if end:
        break

    base = nextR

print(" ".join(map(str,ans)))


Measured memory_bytes: 49904
#include<iostream>
using namespace std;
int main(){
    while(1){
		int k,c,sum=0;
        cin>>k;
        if(k==0)break;
        for(int i=0;i<k*(k-1)/2;i++){
            cin>>c;
            sum+=c;
        }
        cout<<sum/(k-1)<<endl;
    }
    return 0;
}

Measured memory_bytes: 1160
tmp = list(map(int, input().split()))
r = tmp[0]
d = tmp[1]
x0 = tmp[2]

xn = [0] * 11
xn[0] = x0
for i in range(1,11):
  xn[i] = r * xn[i-1] - d
  print (xn[i])

Measured memory_bytes: 38384
//27
#include<iostream>
#include<cctype>

using namespace std;

bool p[20][20][16][4];
int r,c;
char g[20][21];

bool dfs(int,int,int,int);

bool mv(int x,int y,int m,int d){
  int dx[]={1,0,-1,0};
  int dy[]={0,1,0,-1};
  return dfs((x+c+dx[d])%c,(y+r+dy[d])%r,m,d);
}

bool dfs(int x,int y,int m,int d){
  if(p[x][y][m][d]++){
    return false;
  }else{
    char c=g[y][x];
    if(c=='<'){
      d=2;
    }else if(c=='>'){
      d=0;
    }else if(c=='^'){
      d=3;
    }else if(c=='v'){
      d=1;
    }else if(c=='_'){
      d=m?2:0;
    }else if(c=='|'){
      d=m?3:1;
    }else if(c=='?'){
      for(int i=0;i<4;i++){
	if(mv(x,y,m,i)){
	  return true;
	}
      }
      return false;
    }else if(c=='@'){
      return true;
    }else if(isdigit(c)){
      m=c-'0';
    }else if(c=='+'){
      m=(m+1)%16;
    }else if(c=='-'){
      m=(m+15)%16;
    }
    return mv(x,y,m,d);
  }
}

int main(){
  cin>>r>>c;
  for(int i=0;i<r;i++){
    cin>>g[i];
  }
  cout<<(dfs(0,0,0,0)?"YES":"NO")<<endl;
  return 0;
}

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

int main() {
	int n, k, s;
	cin >> n >> k;
	vector<int>l;
	for (int i = 0; i < n; i++) {
		cin >> s; l.push_back(s);
	}
	sort(l.begin(), l.end(),greater<int>());
	int ans = 0;
	for (int i = 0; i < k; i++) {
		ans += l[i];
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

#define debug(x) cout << #x << " : " << x << '\n';

// code //
const long long INF = 1e18;

int main() {
	long long a[4];
	for(int i=0; i<4; ++i)
		cin >> a[i];

	long long ans=-INF;
	for(int i=0; i<4; ++i)
		for(int j=i+1; j<4; ++j) {
			if(i==0&&j==1 || i==2&&j==3)
				continue;
			ans=max(ans, a[i]*a[j]);
		}


	cout << ans;
}

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

int main() {
  int N, M, ans;
  vector<int> A;

  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    int a;
    cin >> a;
    A.push_back(a);
  }

  ans = 0;
  for(int i = 0; i < M; i++) {
    if(A[i] > M)
      ans++;
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3152
/*************************************************\
           In the name of almighty ALLAH
                 MD.Faysal Hasan
                Comilla Univesity
\*************************************************/

#include<bits/stdc++.h>
using namespace std;

#define     ikarus_101  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef     long long             ll;
typedef     long double           ld;
typedef     unsigned long long    ull;
typedef     vector<ll>            vll;
typedef     pair<ll,ll>           pll;
typedef     vector<pll>           vpl;
typedef     map<ll,ll>            mll;
typedef     multiset<ll>          msl;
typedef     multimap<ll,ll>       Mll;
using pqboro=priority_queue<ll,vll,less<ll>>;
using pqchoto=priority_queue<ll,vll,greater<ll>>;

#define    all(str)       str.begin(),str.end()
#define    sajo(str)      sort(str.begin(),str.end())
#define    rev(str)       reverse(str.begin(),str.end())
#define    usajo(str)     sort(str.rbegin(),str.rend())
#define    vin(a)         for(auto &it : a) cin>>it
#define    vout(a)        for(auto it:a) cout<<it<<' ';cout<<nn
#define    vmax(a)        *max_element(all(a))
#define    vmin(a)        *min_element(all(a))
#define    pb             push_back
#define    eb             emplace_back
#define    mkp(x,y)       make_pair(x,y)
#define    F              first
#define    S              second
#define    yes            cout<<"Yes"<<nn
#define    no             cout<<"No"<<nn
#define    nn             "\n" ///endl
#define    rep(i,n)       for (i=0;i<n;++i )
#define    rep1(i,n)      for (i=1;i<=n;++i )

#define    min3(a,b,c)    min(a,min(b,c))
#define    max3(a,b,c)    max(a,max(b,c))
#define    sqr(x)         ((x)*(x))
#define    pi             2*acos(0.0)
#define    gcd(a,b)       __gcd(a,b)
#define    lcm(a,b)       (a/gcd(a,b))*b
#define    mem(a,b)       memset(a,b,sizeof (a))
#define    dec(x)         cout<<fixed<<setprecision(x)
#define    none(n)         __builtin_popcountll(n)

template < typename T > string toString ( T Number ) { stringstream ss ; ss << Number ; return ss.str() ; }
template < typename T > ll toll ( T str ) { stringstream ss ; ss << str ; ll num ; ss >> num ; return num ; }
ll power(ll n , ll k) { if(k == 0) return 1 ; if(k&1) return n*sqr(power(n,k/2)) ; else return sqr(power(n,k/2)); }

const   int  N   =   2e5+7;
const   int  M   =   1e9+7;
const   ll  inf  =   0x7f7f7f7f7f7f7f7f;
const   int dx[] =   {+1,+2,+2,+1,-1,-2,-2,-1};
const   int dy[] =   {-2,-1,+1,+2,+2,+1,-1,-2};

int main() {ikarus_101

    ll n,m,i,j,k,x;



    cin>>n;
    vpl v(n);
    rep(i,n) cin>>v[i].F>>v[i].S;
    double dis = 0.0;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            dis += sqrt(sqr(v[i].F-v[j].F)*1.0+sqr(v[i].S-v[j].S)*1.0);
        }
    }
    dec(10);
    cout << 2.0*dis/(n*1.0) << nn;




    return 0;
}


Measured memory_bytes: 3800
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
const int MaxN = 300;

using namespace std;
int n , m , vis[MaxN + 5] , cnt[MaxN + 5];
int a[MaxN + 5][MaxN + 5];
int used[MaxN + 5];
void Init(){
	memset(vis , 0 , sizeof(vis));
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++){
			scanf("%d" , &a[i][j]);
		}
	}
	for(int i = 1;i <= n;i++) cnt[i] = 1;
}
void Solve(){
	int Min = 1 << 30;
	while(1){
		int Max = 0 , pos = 0;
		for(int i = 1;i <= m;i++) vis[i] = 0;
		for(int i = 1;i <= n;i++){
			while(used[a[i][cnt[i]]]) cnt[i]++;
			if(++vis[a[i][cnt[i]]] > Max){
				Max = vis[a[i][cnt[i]]];
				pos = a[i][cnt[i]];
			}
		}
		Min = min(Min , Max);
		for(int i = 1;i <= n;i++){
			if(vis[a[i][cnt[i]]] == Max){
				used[a[i][cnt[i]]] = 1;
				 cnt[i]++;
				 if(cnt[i] > m) {
				 	 printf("%d\n" , Min);
				 	 return;
				 }
			}
		}
	}
}
int main()
{
	while(~scanf("%d%d" , &n , &m)){
		Init();
		Solve();
	}
}

Measured memory_bytes: 512
import sys


def input():
    return sys.stdin.readline().rstrip()


def tc():
    N = int(input())



def main():
    N = int(input())

    dp = [0]*(N+1)
    rt = int(N **0.5) +1
    for i in range(1,rt):
        ii = i**2
        for j in range(1,rt):
            jj = j**2
            ij = i*j
            if ii + jj + 1 + ij + i + j  >N:
                break
            for k in range(1,rt):
                kk = k**2
                case =int( ii + jj + kk + ij + i*k + j*k )
                if case <=N:
                    dp[case] +=1
                else:
                    break

    print(*dp[1:N+1], sep="\n")









if __name__ == "__main__":
    main()


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

#define ED return 0;
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) int(pow(x,y))
const long long mod = 1000000007;

int main() {
    string s;
    int N;
    cin >> s >> N;
    for(int i = 0;i < s.size();i++){
        if(s.at(i) != '1'){
            cout << s.at(i) << endl;
            ED
        }
        if(i >= N-1){
            cout << 1 << endl;
            ED
        }
    }
    cout << 1 << endl;
}


Measured memory_bytes: 256
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    N, M = iip(True)
    A = iip(True)

    A.sort()
    A.reverse()
    st = sum(A)

    border = st / 4 / M
    res = 0
    #print(A)
    #print(border)
    for a in A:
        if a >= border:
            res += 1

    if res >= M:
        print("Yes")
    else:
        print("No")


def solve():
    N = iip(False)
    S = input()


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_=mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

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

def solve(n,s):
  s_sorted = sorted(s)
  s_sum = sum(s)
  if s_sum % 10 != 0:
    return s_sum
  for a in s_sorted:
    if  a % 10 != 0:
      return s_sum - a
  return 0



def main():
  N = int(input())
  s = [int(input()) for _ in range(N)]
  print(solve(N,s))
  return

if __name__ == '__main__':
  main()


Measured memory_bytes: 9096
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;

int main() {
  int n;
  cin >> n;
  V<ll> x(n), y(n);
  V<ll> h(n);
  rep(i, n) cin >> x[i] >> y[i] >> h[i];

  rep(cx, 101) rep(cy, 101) {
    bool ok = true;
    ll H = -1;
    ll max_h = 1e10;

    rep(i, n) {
      if (h[i] != 0) {
        ll cand = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
        if (H == -1) H = cand;
        if (H != cand || H > max_h) {
          ok = false;
          break;
        }
      } else {
        max_h = min(max_h, abs(x[i] - cx) + abs(y[i] - cy));
        if (H > max_h) {
          ok = false;
          break;
        }
      }
    }
    if (ok) {
      printf("%d %d %ld\n", cx, cy, H);
      return 0;
    }
  }
}


Measured memory_bytes: 3668
#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;


int main(){
	int x,y;
	
	int aN,bN,R;
	while(cin >> aN >> bN >> R , aN){
		vector<int> v[10000];
		for(int i = 0 ; i < aN ; i++){
			scanf("%d%d",&x,&y);
			v[y].push_back(x);
		}
		for(int i = 0 ; i < 10000 ; i++)
			sort(v[i].begin(),v[i].end());
		int D = 4 * R , ans = 0	;
		for(int i = 0 ; i < bN ; i++){
			scanf("%d%d",&x,&y);
			for(int p = -D ; p <= D ; p++){
				if(y+p < 0 || y+p >= 10000) continue;
				int m = sqrt( D*D - p*p );
				ans += upper_bound(v[y+p].begin(),v[y+p].end(),x+m) -
					   lower_bound(v[y+p].begin(),v[y+p].end(),x-m);
			}
		}
		printf("%d\n",ans);
	}
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, t) for (int i = (s); i < (int)(t); i++)
typedef long long ll;
const ll mod = 1e9 + 7;

template<typename T>
vector<T> subvector(vector<T> const &v, int m, int n) {
    auto first = v.cbegin() + m;
    auto last = v.cbegin() + n;
    vector<T> vec(first, last);
    return vec;
}

template<typename T>
vector<vector<T>> combinations(vector<T> &it, int r) {
    vector<vector<T>> comb;
    int n = it.size();
    if (r > n)
        return comb;
    vector<int> indices(r);
    rep(i, r) indices[i] = i;
    vector<T> sub0(r);
    rep(k, r)sub0[k] = it[indices[k]];
    comb.emplace_back(sub0);
    while (true) {
        bool flg = false;
        for (int i = r - 1; i >= 0; i--) {
            if (indices[i] != i + n - r) {
                indices[i]++;
                rep2(j, i + 1, r)indices[j] = indices[j - 1] + 1;
                vector<T> sub(r);
                rep(k, r)sub[k] = it[indices[k]];
                comb.emplace_back(sub);
                flg = true;
                break;
            }
        }
        if (!flg)
            return comb;
    }
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<pair<int, int>> XY(N);
    vector<int> X(N);
    vector<int> Y(N);
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        XY[i] = make_pair(x, y);
        X[i] = x;
        Y[i] = y;
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    ll ans = LLONG_MAX;
    for (vector<int> &xsub: combinations(X, 2)) {
        for (vector<int> &ysub: combinations(Y, 2)) {
            int cnt = 0;
            for (pair<int, int> &p: XY) {
                int x = p.first;
                int y = p.second;
                if (xsub[0] <= x && x <= xsub[1] && ysub[0] <= y && y <= ysub[1]) {
                    cnt++;
                }
            }
            if (K <= cnt) {
                ans = min(ans, (ll)(xsub[1] - xsub[0]) * (ysub[1] - ysub[0]));
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 2000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
vector<pair<long long, long long>> go[200000];
int main() {
#define int long long
	int n, m;
	cin >> n >> m;
	REP(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		go[a].push_back(make_pair(b, c));
	}
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> next;
	next.push(make_pair(0, 1));
	long long ans = 0;
	for (int i = 1; i <= n; ++i) {
		while (next.empty() == false && next.top().second < i) {
			next.pop();
		}
		if (next.empty() == true) {
			cout << -1 << endl;
			return 0;
		}
		ans = next.top().first;
		REP(q, go[i].size()) {
			next.push(make_pair(go[i][q].second + ans, go[i][q].first));
		}
	}
	cout << ans << endl;
}

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

int dp[3004][3004][2];

int main()
{
    int n, t;
    cin >> n >> t;
    int a[3004], b[3004];
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < t; j++){
            dp[i][j][0] = dp[i - 1][j][0];
            dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] + b[i - 1]);
            if(j > 0){
                dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][0]);
                dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][1]);
            }
            if(j >= a[i - 1]){
                dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - a[i - 1]][0] + b[i - 1]);
                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - a[i - 1]][1] + b[i - 1]);
            }
        }
    }
    cout << dp[n][t - 1][1] << endl;
}

Measured memory_bytes: 70656
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000
int n, m, t;
int a[N];
int b[N];
char c[N];
long long d[N];
bool used[N];

void p1(void) {
	int x = (n + 59) / 60;
	int y;
	long long z;
	f(i, x) {
		f(j, n)d[j] = 0;
		y = 60 * i;
		z = 1;
		while (y < n) {
			if (y >= (60 * (i + 1)))break;
			d[y] = z;
			y++;
			z *= 2;
		}
		for (int j = m - 1; j >= 0; j--) {
			d[a[j]] = (d[a[j]] | d[b[j]]);
			d[b[j]] = d[a[j]];
		}
		z = z * 2;
		z--;
		f(j, n)z = z & d[j];
		if (z > 0) {
			y = (60 * i);
			while (z > 0) {
				if (z % 2 == 1)break;
				y++;
				z /= 2;
			}
			f(j, n)used[j] = false;
			used[y] = true;
			for (int j = m - 1; j >= 0; j--) {
				if (used[a[j]])c[j] = '^';
				else c[j] = 'v';
				used[a[j]] = (used[a[j]] | used[b[j]]);
				used[b[j]] = used[a[j]];
			}
			printf("%s\n", c);
			return;
		}
	}
	printf("-1\n");
	return;
}

void p2(void) {
	if (n < 3) {
		printf("-1\n");
		return;
	}
	int x = 0;
	for (int i = m - 1; i >= 0; i--) {
		if (b[i] > 2)c[i] = '^';
		else {
			if ((a[i] == 0) && (b[i] == 1)) {
				if (x == 0)c[i] = '^';
				else c[i] = 'v';
				x = 2;
			}
			if ((a[i] == 0) && (b[i] == 2)) {
				if (x == 0)c[i] = '^';
				else c[i] = 'v';
				x = 1;
			}
			if ((a[i] == 1) && (b[i] == 2)) {
				if (x == 1)c[i] = '^';
				else c[i] = 'v';
				x = 0;
			}
		}
	}
	printf("%s\n", c);


	return;
}



int main() {
	f(i, N) {
		a[i] = 0;
		b[i] = 0;
		c[i] = 0;
	}

	scanf("%d %d %d", &n, &m, &t);
	f(i, m) {
		scanf("%d %d", &a[i], &b[i]);
		a[i]--;
		b[i]--;
	}
	if (t == 1)p1();
	else p2();
	return 0;
}

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

typedef long long ll;
const int inf = 1e9;

int n, ans;

int main(){
	ans = 0;
	cin>>n;
	string s;
	cin>>s;
	for(int l = 0, r = n - 1; l < r;){
		if(s[l]=='W'){
			if(s[r]=='R'){
				swap(s[l], s[r]);
				ans++;
				l++;
			}
			r--;
		}
		else{
			l++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3692
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;


/*
Euclidean Algorithm
 */
ll euclid(ll a, ll b){
  while (b>0){
    a = a % b;
    swap(a, b);
  }
  return a;
}


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

  ll N;
  cin >> N;
  vector<ll> a(N);
  REP(i,N) { cin >> a[i]; }

  ll next = 1;
  ll blk = 0;
  ll ans = 0;
  REP(i,N){
    if (a[i]==next){
      ans += blk;
      blk = 0;
      next++;
    } else {
      blk++;
    }
  }
  ans += blk;
  
  if (next==1){
    ans = -1;
  }

  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 1792