akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n;
    cin >> n;
    VI h(n);
    REP(i,0,n) cin >> h[i];
    int m = h[0];
    int cnt = 1;
    REP(i,1,n) if (h[i] >= m) {
        m = h[i];
        ++cnt;
    }
    cout << cnt << endl;
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(I,X,Y) for(int (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(int (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define INF 1000000007
#define LINF 1000000000000000007
typedef long long ll;
using namespace std;

int main(){
  int N,M,X,Y,maxx=-INF,miny=INF,x,y;
  cin >> N >> M >> X >> Y;
  FOR(i,0,N){
    cin >> x;
    maxx = max(maxx,x);
  }
  FOR(i,0,M){
    cin >> y;
    miny = min(miny,y);
  }
  bool ans = 0;
  FOR(i,maxx+1,miny+1){
    if(X < i && i <= Y)ans = true;
  }
  cout << (!ans ? "War" : "No War") << endl;
}


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

int main(){
    int N;
    cin >> N;
    vector<ll> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    ll ans = 0;
    auto max_it = max_element(a.begin(), a.end());
    int max_index = distance(a.begin(), max_it);
    while (a[max_index] >= N) {
        ll cnt = a[max_index] / N;
        a[max_index] %= N;
        a[max_index] -= cnt;
        for (int i = 0; i < N; i++) a[i] += cnt;
        ans += cnt;
        max_it = max_element(a.begin(), a.end());
        max_index = distance(a.begin(), max_it);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <cmath>
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  int num;
  int count = 0;
  cin >> num;
  while(num > 0){
      if(num%10 == 1){
          count++;
      }
      num /= 10;
  }
  cout << count <<"\n";
}


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

int main()
{
	int n,i;
	cin>>n;
	int h[n+1];
	for(i=1;i<=n;i++)
	cin>>h[i];
	int dp[n+1];
	dp[1]=0;
	dp[2]=abs(h[2]-h[1]);
	for(i=3;i<=n;i++)
	dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
	cout<< dp[n];
}


Measured memory_bytes: 1024
import sys

x = int(input())

b = 0
ans=(-1,-1)
while True:
    a5 = b**5 + x

    # 判断a是不是整数5次方
    a = b+1
    if a**5>a5:
        break
    while a**5<a5:
        a+=1
    if a**5==a5:
        ans=(a,b)
        break

    b+=1

if ans[0]!=-1:
    print(ans[0],ans[1])
    sys.exit(0)

b=-1
while True:
    a5=b**5+x

    a=b+1
    while a**5<a5:
        a+=1
    if a**5==a5:
        ans=(a,b)
        break

    b-=1

print(ans[0],ans[1])

Measured memory_bytes: 9128
import java.util.Scanner

import scala.math.BigDecimal.RoundingMode._
object Main extends App {

  val sc = new Scanner(System.in)
  while(sc.hasNext){
    val line = sc.nextLine()
    val n =  line.split(" ").map {_.toDouble}
    val a = n(0)
    val b = n(1)
    val c = n(2)
    val d = n(3)
    val e = n(4)
    val f = n(5)

    var x :BigDecimal = BigDecimal((b*f-e*c) / (b*d-a*e)).setScale(3, HALF_UP)
    var y :BigDecimal = ((c - a * x) / b).setScale(3, HALF_UP)

    if(x==0)x=0;
    if(y==0)y=0;
    println(f"$x%.3f $y%.3f")
  }
}

Measured memory_bytes: 45608
#include<iostream>

#define LL  long long
using namespace std;
#define MAXN    200010

int N;
int a[MAXN];
int cnt[MAXN];

int main()
{
    cin>>N;
    for(int i=0; i<N-1; i++) {
        scanf("%d", &a[i]);
        ++cnt[a[i]];
    }

    for(int i=1; i<=N; i++) {
        printf("%d\n", cnt[i]);
    }
    return 0;
}

Measured memory_bytes: 5296
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
using namespace std;

int main()
{
	int N,X,t,ANS=2;
	vector<int> M;
	vector<int> MM;
	cin >> N >> X;
	for (int i = 0; i < N; i++)
	{
		cin >> t;
		M.push_back(t);
	}
	t = 0;
	MM.push_back(0);
	MM.push_back(M[0]);
	if (MM[1] < X) {
		for (int i = 2; i < N + 1; i++)
		{
			t = MM[i - 1];
			MM.push_back(M[i - 1] + t);
			if (MM[i] <= X)
			{
				ANS++;
			}
		}
		cout << ANS << endl;
	}
	else {
		cout << "0" << endl;
	}
}

Measured memory_bytes: 256
import java.io.*; 
import java.util.*;

class Main //for atcoder
{ 
	public static void main (String[] args) throws IOException
	{ 
		    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        
	        String[] ip;
	       
	            
	            ip = br.readLine().trim().split("\\s+");
				int n = Integer.parseInt(ip[0]);
				int k = Integer.parseInt(ip[1]);
	            
	            ip = br.readLine().trim().split("\\s+");
	            int[] arr = new int[n];
	            for(int i=0;i<n;i++){
	                arr[i] = Integer.parseInt(ip[i]);
	            }
	            fun(arr,n,k);


	
	} 

	static void fun(int[] arr,int n,int k){

		int[] dp = new int[n];

		dp[0]=0;
		dp[1] = Math.abs(arr[1]-arr[0]);

		for(int i=2;i<n;i++){
			dp[i] = Integer.MAX_VALUE;
		}

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


			for(int j=i-1;j>=i-k;j--){


				
				
				if(j>=0)
				dp[i] = Math.min(dp[i], Math.abs(arr[i]-arr[j]) + dp[j]);

			}

		

		
		


		}

		
			System.out.print(dp[n-1]);
	}

	
} 



Measured memory_bytes: 45988
#include <iostream>
#include <cstdlib>
#include <queue>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

long long gcd(long long a, long long b) {
    long long r;
    while (b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return (a / gcd(a, b)) * b;
}

int main()
{
    int n;
    long long ans=0;
    cin >> n;
    vector<long long> t(n);
    for(int i=0; i<n; ++i){
        cin >> t[i];
    }
    sort(t.begin(), t.end());
    if(n == 1){
        ans = t[0];
    }
    else {
        for(int i=1; i<n; ++i){
            if(i == 1){
                ans = lcm(t[0], t[1]);
            }
            else {
                ans = lcm(ans, t[i]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = --end(s); i != begin(s); --i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
#define rall(f,x,...) [&](decltype(x)& whole) { return (f)(rbegin(whole), rend(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e17;
ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.size(); }
template<class T> constexpr T pow2(const T a) { return a * a; }
template<class T, class ... Args> constexpr T mins(T& a, Args... args) { return a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr T maxs(T& a, Args... args) { return a = max<T>({ a,args... }); }
template<typename A, size_t N, typename T>
void fillArray(A(&array)[N], const T& val) { std::fill((T*)array, (T*)(array + N), val); }


int n;
double x[55], y[55];
void solve() {
    cin >> n;
    rep(i, n) cin >> x[i] >> y[i];

    double l = 0, r = 2000;
    while (r - l > 1e-7) {
        auto mid = (l + r) / 2;

        bool ok = false;
        rep(j, n) {
            rep(i, j) {
                double dist = hypot(x[i] - x[j], y[i] - y[j]);
                if (dist > 2 * mid) continue;
                double h = sqrt(mid * mid - (dist / 2) * (dist / 2));
                pair<double, double> vec{ (y[i] - y[j]) * h / dist, -(x[i] - x[j]) * h / dist };
                pair<double, double> m{ (x[i] + x[j]) / 2,(y[i] + y[j]) / 2 };
                pair<double, double> p[] = {
                    {m.first + vec.first,m.second + vec.second},
                    {m.first - vec.first,m.second - vec.second}
                };

                rep(s, 2) {
                    bool res = true;
                    rep(k, n) {
                        if (k == i || k == j) continue;
                        double d = hypot(x[k] - p[s].first, y[k] - p[s].second);
                        if (d > mid) { res = false; break; }
                    }
                    ok |= res;
                }

                if (ok) break;
            }
            if (ok) break;
        }

        if (ok) r = mid;
        else l = mid;
    }

    cout << r << endn;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout << flush;
    return 0;
}


Measured memory_bytes: 384
import java.util.*;
import java.awt.geom.*;
public class Main {
	//2337 start

	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n == 0) break;
			while(n-- > 0){
				int m = sc.nextInt();
				Line2D [][] data = new Line2D[m][4];
				for(int i = 0 ; i< m; i++){
					Point2D [] input = new Point2D[4];
					for(int j = 0; j < 4; j++){
						int x = sc.nextInt();
						int y = sc.nextInt();
						input[j] = new Point2D.Double(x, y);
					}
					
					for(int j = 0 ; j< 4; j++){
						data[i][j] = new Line2D.Double(input[j], input[(j+1) % 4]);
					}
				}
				solve(data, m);
			}
		}
	}
	
	private void solve(Line2D[][] data, int m) {
		UnionFind uf = new UnionFind(m);
		for(int i = 0 ; i < m ;i++){
			for(int j = i+1; j < m; j++){
				if(intersect(data[i], data[j])){
					uf.unite(i, j);
				}
			}
		}
		System.out.println(uf.num);
	}

	private boolean intersect(Line2D[] l, Line2D[] m) {
		for(int i = 0 ; i < l.length ; i++){
			for(int j = 0 ; j < m.length; j++){
				if(l[i].intersectsLine(m[j])){
					return true;
				}
			}
		}
		
		int temp = l[0].relativeCCW(m[0].getP1());
		boolean flg = true;
		for(int i = 1 ; i < l.length; i++){
			if(l[i].relativeCCW(m[0].getP1()) * temp < 0 ){
				flg = false;
				break;
			}
		}
		if(flg) return true;
		
		temp = m[0].relativeCCW(l[0].getP2());
		flg = true;
		for(int i = 1; i < m.length; i++){
			if(m[i].relativeCCW(l[0].getP2()) * temp < 0){
				return false;
			}
		}
		return true;
	}

	class UnionFind{
		int [] par, rank;
		int num;

		public UnionFind(int n) {
			par = new int[n];
			rank = new int[n];
			for(int i = 0 ; i < n; i++){
				par[i] = i;
				//rank[i] = 0;
			}
			num = n;
		}
		int find(int x){
			if(par[x] == x)return x;
			else return par[x] = find(par[x]);
		}
		void unite(int x, int y){
			x = find(x);
			y = find(y);
			if(x == y) return ;
			if(rank[x] < rank[y]) par[x] = y;
			else{
				par[y] = x;
				if(rank[x] == rank[y]) rank[x]++;
			}
			num--;
		}
		boolean same(int x, int y){
			return find(x) == find(y);
		}
	}

	public static void main(String[] args) {
		Main obj = new Main();
		obj.doit();
	}
}

Measured memory_bytes: 12000
#include <algorithm> //STLͨ���㷨
#include <cmath> //������ѧ����
#include <cstdio> //��������/�������
#include <iostream> //����������/���
#include <cstring> //�ַ�������
#include <string> //�ַ�����
#include <ctime> //�������ʱ��ĺ���
#define itn int
#define fro for
#define ll long long
#define reg register
#define inf 1234567890
#define rep(i,a,b,c) for (int i=a;i<=b;i+=c)
/*#include <bitset> //STLλ������
#include <cstype> //�ַ�����
#include <cerrno> //���������
#include <complex> //������
#include <clocale> //���屾�ػ�����
#include <cstdlib> //������������ڴ���亯��
#include <deque> //STL˫�˶�������
#include <exception> //�쳣������
#include <fstream> //�ļ�����/���
#include <functional> //STL�������㺯��(���������)
#include <limits> //�����������������ֵ����
#include <list> //STL�����б�����
#include <map> //STLӳ������
#include <iomanip> //����������/���
#include <ios> //��������/���֧��
#include <iosfwd> //����/���ϵͳʹ�õ�ǰ������
#include <istream> //����������
#include <ostream> //���������
#include <queue> //STL��������
#include <set> //STL��������
#include <sstream> //�����ַ�������
#include <stack> //STL��ջ����
#include <stdexcept> //��׼�쳣��
#include <streambuf> //�ײ�����/���֧��
#include <utility> //STLͨ��ģ����
#include <vector> //STL��̬��������
#include <cwchar.h>//���ַ�����������/���
#include <cwctype.h> //���ַ�����*/

using namespace std;

int ans;

int max(int x,int y){return x>y?x:y;}

int min(int x,int y){return x<y?x:y;}

int abs(int x){return x>0?x:-x;}

int gcd(int x,int y){return (!y)?x:gcd(y,x%y);}

void exgcd(int a,int b,int &d,int &x,int &y){if (!b){d=a,x=1,y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}}

int quick_power(ll a,int b){ll r=1;for (;b;b>>=1,a=a*a)if (b&1) r=r*a;return r;}

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig = false, c = read(); !isdigit(c); c = read()) {
		if (c == '-') iosig = true;
		if (c == -1) return;
	}
	for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
	if (iosig) x = -x;
}

char sr[10000000],z[20];int C=-1,Z=0;
void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(int x){
	if (x<0) sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
//int find(int x){return fa[x]=fa[x]==x?x:find(fa[x]);}

//void add(int x,int y,int z){to[++cnt]=y;v[cnt]=z;Next[cnt]=head[x];head[x]=cnt;}
int du[100];
int main()
{
	int n,m;
	read(n);read(m);
	for (int i=1;i<=m;i++)
	{
		int q,w;
		read(q),read(w);
		du[q]++;du[w]++;
	}
	for (int i=1;i<=n;i++) print(du[i]);
	Ot();
	return 0;
}









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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    i64 N, T; cin >> N >> T;
    vector<i64> A(N);
    REP(i, N) cin >> A[i];

    vector<i64> M(N + 1, 0);
    REP(i, N) M[i + 1] = max(M[i], A[N - 1 - i]);

    i64 n_apple = T / 2;
    i64 maxp = 0;
    i64 cnt = 0;
    REP(i, N) {
        i64 p = (M[N - 1 - i] - A[i]) * n_apple;
        if (p > maxp) maxp = p, cnt = 1;
        else if (p == maxp) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 4748
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<map>
#include<cstdint>
#include<unordered_map>
#include<boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < ( int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second

namespace mp = boost::multiprecision;

using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int>A(n);
	vector<ll>sum(n + 1);

	rep(i, n) {
		scanf("%d", &A[i]);
		A[i] -= (i + 1);
	}
	sort(all(A));
	sum[0] = 0;
	ll Sum = 0;
	rep(i, n) {
		Sum += A[i];
		sum[i + 1] = Sum;
	}
	ll ans = 1e20;
	FOR(ite, 0, n) {
		ll tmp = (ll)(n - 2 * ite)*A[ite] * (-1) + (sum[n] - 2 * sum[ite]);
		ans = min(ans, tmp);
	}
	cout << ans << endl;

}


Measured memory_bytes: 2560
#!/usr/bin/env python3
#第二回全国統一プログラミング王決定戦予選 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
d = LI()
if d[0] != 0:
    print(0)
    quit()
d.sort()
d = list(Counter(d).items())
n = len(d)
if d[0][1] > 1:
    print(0)
    quit()
ans = 1
for i in range(1,n):
    j,k = d[i]
    l,m = d[i-1]
    if j != l+1:
        print(0)
        quit()
    ans *= m**k
    ans %= mod
print(ans)


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

int n,a[405];
LL dp[405][405],sum[405];

LL doit(int fr,int to) {
	if (fr == to) return 0;
	if (dp[fr][to] >= 0) return dp[fr][to];
	dp[fr][to] = 1e15;
    for (int i=fr; i<to; i++) {
		dp[fr][to] = min(dp[fr][to], doit(fr,i)+doit(i+1,to)+sum[to]-sum[fr-1]);
    }
    return dp[fr][to];
}

int main() {
	scanf("%d",&n);
	sum[0] = 0;
	for (int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
		sum[i] = sum[i-1]+a[i];
	}
	memset(dp,-1,sizeof(dp));
	printf("%lld\n",doit(1,n));
	return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

struct cww{cww(){
    ios::sync_with_stdio(false);cin.tie(0);
}}star;

#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}


typedef vector<LL> V;
typedef vector<V> VV;
const LL INF=1e15;
int a[212345];
int b[212345];
LL c[212345];
LL d[212345];
int main(){
    int N,M,s,t;
    cin>>N>>M>>s>>t;s--;t--;
    V dist(N,INF);
    VV g(N);
    REP(i,N)cin>>d[i];
    REP(i,M){
        cin>>a[i]>>b[i];
        a[i]--;b[i]--;
        c[i]=d[b[i]];
        g[a[i]].pb(i);
    }
    REP(i,N-1){
        a[i+M]=i+1;
        b[i+M]=i;
        c[i+M]=0;
        g[a[i+M]].pb(i+M);
    }
    dist[s]=0;
    priority_queue<pair<LL,int>> Q;
    Q.push({0ll,s});
    while(Q.size()){
        auto q=Q.top();Q.pop();
        LL cost=-q.fi;
        int v=q.se;
        if(cost>dist[v])continue;
        for(auto &e:g[v]){
            int u=b[e];
            LL nxtcost=c[e]+cost;
            if(chmin(dist[u],nxtcost)){
                Q.push({-nxtcost,u});
            }
        }
    }
    cout<<dist[t]<<endl;
    return 0;
}

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

const int INF = 1001001001;

int main() {
	int a, b, c, d, e;
	cin >> a >> b >> c >> d >> e;
	vector<int> v = {a, b, c, d, e};
	vector<int> p = {0, 1, 2, 3, 4};
	int best_answer = INF;
	do {
		int ans = 0;
		rep(i, v.size()) {
			while (ans%10 != 0) ++ans;
			ans += v[p[i]];
		}
		best_answer = min(best_answer, ans);
	} while (next_permutation(p.begin(), p.end()));
	cout << best_answer << endl;
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
//#include<cmath>
//#include<iostream>
using namespace std;

int main(){
	int n, i, a,b,c,d;

	while(~scanf("%d", &n)){

	for(i=0, a=0; a<10; a++){
		for(b=0; b<10; b++){
			for(c=0; c<10; c++){
				for(d=0; d<10; d++){
if(a+b+c+d==n) i++;	
				}
			}
		}
	}

	printf("%d\n", i);
	}
 return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <list>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int visited[100001] = {0};
vector<int> b[100001];

void dfs (int i) {
  if(visited[i] == 1) {
    return; 
  }
  visited[i] = 1;
  for (auto j: b[i]) {
    dfs(j);
  }
  return;
}

int main() {
  int N, M;
  cin >> N >> M;
  for (int i = 1; i <= M; i++) {
    int x, y, z = 0;
    cin >> x >> y >> z;
    b[x].push_back(y);
    b[y].push_back(x);
  }
  
  int ans = 0;
  for (int i = 1; i <=N; i++) {
    if (visited[i] == 0) {
      dfs(i);
      ans++;
    }
  }
  
  cout << ans;

  return 0;
}


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

#define INF (1LL << 31 - 1)
#define MOD int(1e9+7)
#define repi(i,j,n) for(int i = (j); i < (n); ++i)
#define rep(i,n) repi(i,0,n)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()

inline void init() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

using ll = long long;

struct T {
  int x, y, id;
  T () {}
  T (ll x, ll y, ll id) : x(x), y(y), id(id) {}
  bool operator < (const T &t) const {
    if (x == t.x) return y < t.y;
    return x < t.x;
  }
};

ll R, C, n, a, b, c, d;
vector<T> xz, yz, xr, yc;
vector<T> v;

int main() {
  init();
  cin >> R >> C >> n;
  rep(i,n) {
    cin >> a >> b >> c >> d;
    if ((a == 0 or a == R or b == 0 or b == C) and
        (c == 0 or c == R or d == 0 or d == C)) {
      if (a == 0) xz.push_back({a, b, i});
      else if (a == R) xr.push_back({a, b, i});
      else if (b == 0) yz.push_back({a, b, i});
      else yc.push_back({a, b, i});
      if (c == 0) xz.push_back({c, d, i});
      else if (c == R) xr.push_back({c, d, i});
      else if (d == 0) yz.push_back({c, d, i});
      else yc.push_back({c, d, i});
    }
  }

  int sxz, syz, sxr, syc;
  sxz = xz.size();
  syz = yz.size();
  sxr = xr.size();
  syc = yc.size();

  sort(all(xz));
  sort(all(yz));
  sort(all(xr));
  sort(all(yc));
  //cout << "size : " << sxz << " " << syz << " " << sxr << " " << syc << endl;
  rep(i,sxz) v.push_back({xz[i].x, xz[i].y, xz[i].id});
  rep(i,syc) v.push_back({yc[i].x, yc[i].y, yc[i].id});
  for (int i = sxr - 1; i >= 0; i--) v.push_back({xr[i].x, xr[i].y, xr[i].id});
  for (int i = syz - 1; i >= 0; i--) v.push_back({yz[i].x, yz[i].y, yz[i].id});
  

  stack<T> st;
  map<int, bool> mp;

  int si = v.size();
  /*cout << "------------------------" << endl;
  rep(i,si) cout << v[i].x << " " << v[i].y << endl;
  cout << "------------------------" << endl;*/
  
  rep(i,si) {
    //cout << v[i].x << " " << v[i].y << " " << v[i].id << endl;
    if (!mp[v[i].id]) {
      st.push(v[i]);
      mp[v[i].id] = true;
    }
    else {
      T t = st.top();
      //cout << "st.top = " << t.x << " " << t.y << " " << t.id << endl;
      st.pop();
      if (t.id != v[i].id) {
        cout << "NO" << endl;
        return 0;
      }
      else {
        mp[v[i].id] = false;
      }
    }
  }

  cout << "YES" << endl;

  return 0;
}


Measured memory_bytes: 10628
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
x = sorted(x, reverse=True)[0]
y = list(map(int, input().split()))
y = sorted(y)[0]


for z in range(-100, 101):
    if X < z <= Y and z <= y and x < z:
        print('No War')
        break
else:
    print('War')


Measured memory_bytes: 9104
#include <bits/stdc++.h>
using namespace std;
int main(){
    int64_t n, k;
    cin >> n >> k;
    int64_t a[2100];
    for(int64_t i=0; i<n; i++){
        cin >> a[i];
    }

    int64_t ans = 0;
    for(int64_t i=0; i<n; i++){
        int64_t leftRev = 0;
        int64_t rightRev = 0;
        for(int64_t j=0; j<i; j++){
            if(a[j]<a[i]){
                leftRev++;
            }
        }
        for(int64_t j=i+1; j<n; j++){
            if(a[i]>a[j]){
                rightRev++;
            }
        }
        ans += ( ((rightRev*k)%1000000007) + ( ( (leftRev+rightRev)*k % 1000000007 * (k-1) % 1000000007 * 500000004 % 1000000007) ) );
    }
    cout << ans%1000000007 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <stdio.h>

int main(void){
  int n;
  std::cin >> n;
  n = n%1000;
  if(n==0){
    std::cout << "0";
    exit(0);
  }
  std::cout << 1000-n;
  return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h> 
typedef long long ll;
using namespace std;
const ll mod =1e9 + 7; 
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,dp[105][105];
char ch[105][105];
int main(){
	int i,j,op;
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    n=read(),m=read();
    for(i=1;i<=n;i++) scanf("%s",ch[i]+1);
    memset(dp,0x3f,sizeof(dp));
	if(ch[1][1]=='#') dp[1][1]=1;
    else dp[1][1]=0;
    for(i=1;i<=n;i++){
    	for(j=1;j<=m;j++){
    		if(i>=2){
    			op=0;
    			if(ch[i][j]=='#') op=(ch[i-1][j]=='.')?1:0;
    			dp[i][j]=min(dp[i][j],dp[i-1][j]+op);
    		}
    		if(j>=2){
    			op=0;
    			if(ch[i][j]=='#') op=(ch[i][j-1]=='.')?1:0;
    			dp[i][j]=min(dp[i][j],dp[i][j-1]+op);
    		}
    	}
    }
    printf("%d\n",dp[n][m]);
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb(in,tmp) in.push_back(tmp)
#define all(in) in.begin(),n.end()
#define PI acos(-1)
using namespace std;
int main(){
  bool in[30]={false};
  rep(i,28){
    int tmp;
    cin>>tmp;
    in[tmp-1]=true;
  }
  rep(i,30)if(!in[i])cout<<i+1<<endl;

}
/*int main(){

  int a[30]={0};
  rep(i,28){
    int tmp;
    cin>>tmp;
    a[--tmp]++;
  }
  rep(i,30)if(!a[i])cout<<i+1<<endl;


}*/

Measured memory_bytes: 1160
#include<iostream>
using namespace std;
int main(){
  int M_1,M_2,D_1,D_2;
  cin >> M_1 >> D_1 >> M_2 >> D_2;
  if ( M_1 != M_2) {
    cout << "1" << endl;
  }
  else {
    cout << "0" << endl;
  }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
template <class T> void cumulative_sum( T array, size_t N );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;

typedef struct {
	vector <int> to;
	int cost;
} edge;
typedef struct {
	bool a;
	bool b;
} P;
int main( void ){
	string s, t;
	int N, cnt = 0; cin >> N >> s >> t;
	if (s == t){
		cout << N << endl;
		return 0;
	}
	rep(i,1,N){
		bool can = true;
		rep(j,0,i){
			if (s[N-i+j] != t[j]){
				can = false;
				break;
			}
		}
		if (can)
			cnt = i;
	}
	cout << 2*N-cnt << endl;
}

int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
template <class T> void cumulative_sum( T array, size_t N ) {
	rep( i, 1, N + 1 ){
		array[ i ] += array[ i - 1 ];
	}
}
template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}


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

int main() {
    int A, B;
    cin >> A >> B;
    vector<int> v1(A), v2(B);
    for(int i=0; i<A; ++i) {
        cin >> v1[i];
    }
    for(int i=0; i<B; ++i) {
        cin >> v2[i];
    }
    int res = 0;
    for(int i=0; i<B; ++i) {
        int r = i;
        for(int j=0; j<A && r<B; ++j) {
            if(v2[r] == v1[j]) {
                r++;
            }
        }
        res = max(res, r - i);
    }
    cout << res << endl;
}


Measured memory_bytes: 3148
import java.io.*;
import java.util.*;
public class Main {
	public static void main (String[] args) {
	    Scanner s=new Scanner(System.in);
	int n=s.nextInt();
	int a[]=new int[n];
	for(int i=0;i<n;i++){
	    a[i]=s.nextInt();
	    
	}
	
	int c=1;
	boolean f=false;
	for(int i=0;i<n;i++){
	    if(a[i]==c)
	    {
	        c++;
	        f=true;
	    }
	}
	if(f)
	System.out.println(n-c+1);
	else
	System.out.println(-1);
	    
	}
}

Measured memory_bytes: 85204
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int n; cin >> n; 
	vector<ll> punkt(n);
	ll chokudai = 0;
	for( int i = 0; i < n; ++i ){
		ll a, b; cin >> a >> b;
		chokudai += a;
		punkt[i] = a+b;
	}
	sort( punkt.begin(), punkt.end(), greater<ll>() );
	for( int i = 1; i < n; i += 2 ){
		chokudai -= punkt[i];
	}
	cout << chokudai << endl;
	return 0;
}

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
using namespace std;

typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> ii;
typedef pair<int64, int64> int64int64;
typedef vector<int> vint;
typedef vector<int64> vint64;
typedef vector<uint64> vuint64;
typedef vector<vint> vvint;
typedef vector<vint64> vvint64;
typedef vector<vuint64> vvuint64;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;

#define mp make_pair
#define pb push_back
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define fori(n) for(int i = 0; i < n; ++i)
#define forj(n) for(int j = 0; j < n; ++j)
#define fork(n) for(int k = 0; k < n; ++k)
#define INF9 (int64)(1e9)
#define INF18 (int64)(1e18)

template<typename T>
struct compF{
	bool operator()(const pair<T, T> &a, const pair<T, T> &b){
		return a.first < b.first;
	}
};

template<typename T>
struct compS{
	bool operator()(const pair<T, T> &a, const pair<T, T> &b){
		return a.second < b.second;
	}
};

template<typename T>
void printMatrix(const string &txt, vector<vector<T>> &a){
	cout << txt;
	fori(a.size()){
		forj(a[i].size())
			cout << a[i][j] << ' ';

		cout << endl;
	}
}

template<typename T>
void printVector(const string &txt, vector<T> &a){
	cout << txt;
	for (int i = 0; i < a.size(); ++i)
		cout << a[i] << ' ';
	cout << endl;
}

template<typename T>
void readVector(int n, vector<T> &a){
	if (a.size() < n)
		a.resize(n);

	fori(n) cin >> a[i];
}

template<typename T1, typename T2>
bool exist(map<T1, T2> &m, T1 x){
	if (m.find(x) == m.end())
		return false;

	return true;
}

int64 gcd(int64 a, int64 b){
	while (a != 0 && b != 0){
		if (b > a)
			b %= a;
		else
			a %= b;
	}

	return a + b;
}

int64 minFactor(int64 x){
	for (int64 i = 2; i * i <= x; ++i)
		if (x % i == 0)
			return i;

	return x;
}

int64 allFactors(int64 x, vint64 &prms, vint64 &prm_cnt){
	prms.clear();
	prm_cnt.clear();
	while (x > 1){
		int64 t = minFactor(x);
		prms.push_back(t);
		int s = prms.size() - 1;
		prm_cnt.push_back(0);
		while (x % t == 0){
			x /= t;
			++prm_cnt[s];
		}
	}

	return 0;
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie();
	
	int n;
	cin >> n;

	vvint  g(n);
	fori(n - 1){
		int u, v;
		cin >> u >> v;

		--u; --v;

		if (u < v)
			g[v].push_back(u);
		else
			g[u].push_back(v);
	}

	vint64 a(n, 0);
	a[0] = 1;
	for (int i = 1; i < n; ++i){
		a[i] = a[i - 1];
		if (g[i].size()){
			g[i].push_back(-1);
			g[i].push_back(i);
			sort(ALL(g[i]));

			int t = 1;
			int s = g[i].size();
			for (int j = g[i].size() - 1; j > 0; --j){
				a[i] += t * (g[i][j] - g[i][j - 1]);
				--t;
			}
		}
		else
			a[i] += i + 1;
	}

	int64 res = 0;
	fori(n) res += a[i];

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 15584
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(ReadLine());
        while (N > 0)
            N = N - 1000;

        N = N * -1;
        Console.WriteLine(N);
    }

}

Measured memory_bytes: 27500
#include <stdio.h>
#include <math.h>

#define N 10000

int main(){
  int A[N] = {0};
  int length;
  int i = 0, flag = 0;
  int j;
  int count = 0;
  
  scanf("%d", &length);
  while(i < length){
    scanf("%d", &A[i]);
    i++;
  }
  
  for(i = 0; i < length; i++){
    flag = 0;
    
    if(A[i] >2 && A[i]%2 == 0){
      continue;
    }
    
    for(j = 3; j <= sqrt(A[i]); j+=2){
      if(A[i]%j == 0){
	flag = 1;
	break;
      }
    }
    
    if(flag == 0){
      count++;
    }
  }
  printf("%d\n", count);
  return 0;
}



Measured memory_bytes: 2072
#include<stdio.h>
#include<string.h>
char str[9];
int j = 0;
int k;
int main() {
	scanf("%s", str);
	k = strlen(str)-1;
	if (str[0] != 'A') {
		printf("WA");
		return 0;
	}
	else {
		str[0] = 97;
	}
	for (int i = 2; i<k; i++) {
		if (str[i] == 'C') {
		j++;
		str[i] = 97;
		}
	}
	if (j != 1) {
		printf("WA");
		return 0;
	}
	for (int i = 0; i <= k; i++) {
		if (str[i] > 122 || str[i] < 97) {
			printf("WA");
			return 0;
		}
	}
	printf("AC");
}

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

int main(){
  int a,b,c; cin>>a >>b >>c;
  int k; cin>>k;
  int max3 = max(a,max(b,c));
  if(max3 == a){
    a=0;
  }else if(max3 == b){
    b=0;
  }else{
    c=0;
  }
  for(int i=0;i<k;i++){
    max3 *= 2;
  }
  cout<<a+b+c+max3<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    char s[5];



    scanf("%s",s);

    if((s[0]=='A') && (s[1]=='B') && (s[2]=='A'))
        printf("Yes\n");
    else if((s[0]=='B') && (s[1]=='A') && (s[2]=='A'))
        printf("Yes\n");
    else if((s[0]=='A') && (s[1]=='A') && (s[2]=='B'))
        printf("Yes\n");
    else if((s[0]=='B') && (s[1]=='A') && (s[2]=='B'))
        printf("Yes\n");
    else if((s[0]=='A') && (s[1]=='B') && (s[2]=='B'))
        printf("Yes\n");
    else if((s[0]=='B') && (s[1]=='B') && (s[2]=='A'))
        printf("Yes\n");



    else
            printf("No\n");

    return 0;
}


Measured memory_bytes: 128
import bisect
import sys
input = sys.stdin.readline
A,B,Q=map(int,input().split())

Z=[-10**10]
T=[-10**10]

for i in range(A):
    s=int(input())
    Z.append(s)
Z.append(10**11)
for i in range(B):
    t=int(input())
    T.append(t)
T.append(10**11)
    
for i in range(Q):
    x=int(input())
    a=max(Z[bisect.bisect_left(Z,x)],T[bisect.bisect_left(T,x)])-x
    b=x-min(Z[bisect.bisect_left(Z,x)-1],T[bisect.bisect_left(T,x)-1])
    c=Z[bisect.bisect_left(Z,x)]-T[bisect.bisect_left(T,x)-1]+(x-T[bisect.bisect_left(T,x)-1])
    d=Z[bisect.bisect_left(Z,x)]-T[bisect.bisect_left(T,x)-1]+(Z[bisect.bisect_left(Z,x)]-x)
    e=T[bisect.bisect_left(T,x)]-Z[bisect.bisect_left(Z,x)-1]+(x-Z[bisect.bisect_left(Z,x)-1])
    f=T[bisect.bisect_left(T,x)]-Z[bisect.bisect_left(Z,x)-1]+(T[bisect.bisect_left(T,x)]-x)
    print(min(a,b,c,d,e,f))

Measured memory_bytes: 12228
#include<stdio.h>
int main(void){
  char a[3],b[3];
  int sum=0;
    scanf("%s\n",a);
    scanf("%s",b);
  for(int k=0;k<3;k++){
  	if(a[k]==b[k]){
    	sum++;
    }
  }
  printf("%d",sum);
  return 0;
              
}

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

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 100005;
const ll lmod = 1e9+7;

int next(int pre,int now,const char &c){
  int res;
  if(!now){
    // now -> 'S'
    if(c=='o') res = pre;
    else res = pre^1;
  }else{
    // now -> 'W'
    if(c=='o') res = pre^1;
    else res = pre;
  }
  return res;
}

int main(){
  int N; string S;
  cin >> N >> S;
  map<int,string> mp;
  mp[0] = "S"; mp[1] = "W";
  rep(i,2) rep(j,2){
    int pre,now;
    pre = i; now = j;
    string ans = mp[i] + mp[j];
    rep(k,N-1){
      pre = next(pre,now,S[k+1]);
      if(k!=N-2) ans += mp[pre];
      swap(now,pre);
    }
    if(now==i&&next(j,i,S[0])==pre){
      cout << ans << endl;
      return 0;
    }
  }
  cout << "-1" << endl;
  return 0;
}


Measured memory_bytes: 776
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define mp(a,b) make_pair(a,b)
#define SZ(a) ((int)(a).size())
typedef pair<int,int> PI;


int main(){

  map<pair<PI,int>,int > dd;

  {
    int y=1,m=1,d=1;
    while(y<1000){
      int sz=dd.size();
      dd[mp(mp(y,m),d)] = 196470-sz;


      // cout << y << " " << m << " " << d << endl;
      // if(SZ(dd)>600) return 0;
      
      ++d;

      
      if(d==21 || (d==20 && (y%3!=0 && m%2==0))){
        //cout << d << endl;
        
        //if(SZ(dd)>1000) return 0;
        d=1;
        ++m;
        if(m==11){
          //cout << endl;
          m=1;
          ++y;
        }
      }
    }
  }
  
  int n;
  cin >> n;
  rep(i,n){
    int y,m,d;
    cin >> y >> m >> d;
    cout << dd[mp(mp(y,m),d)] << endl;
  }
}

Measured memory_bytes: 13472
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

    h1, m1, h2, m2, k = map(int, input().split())
    all_time = (h2-h1)*60+(m2-m1)
    print(all_time-k)

    



Measured memory_bytes: 9180
n = int(input())
l = [list(map(int,input().split())) for i in range(n-1)]
for i in range(n):
    ans = 0
    if i == n-1:
        print(0)
        exit()
    for j in range(i,n-1):
        ans = l[j][0]+l[j][1]+l[j][2]*(max(((ans-l[j][1]+l[j][2]-1)//l[j][2]),0))

    print(ans)


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

// low以上high以下のbaseの倍数の数
ll baisu(ll base, ll low, ll high){
    ll bt = (low + base - 1) / base;
    ll up = high / base;
    return up - bt + 1;
}

int main(){
    ll n, k;
    cin >> n >> k;
    if(k == 0) {
        cout << n * n << endl;
        return 0;
    }
    ll ans = 0;
    rep(b, 1, n+1) {
        if(b <= k) continue;
        auto uni = baisu(b, 1, n);
        ans += uni * (b - k);
        ll rem = n - uni * b;
        ans += max(0LL, rem - k + 1);
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main()
{
    int a[200005];
    for(int i = 0; i < 200005; i++){
        a[i] = 0;
    }
    int n;
    cin >> n;
    for(int i = 2; i <= n; i++){
        int p;
        cin >> p;
        a[p]++;
    }
    for(int i = 1; i <= n; i++){
        cout << a[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 4416
#include<bits/stdc++.h>
long long int MOD = 1000000007;
using namespace std;
//g++ -std=c++14
//setprecision(10)
int main(){
	int n, l;
	cin >> n >> l;
	vector <string> s(n);
	for(int i = 0; i < n; i++)
		cin >> s[i];
	sort(s.begin(), s.end());
	for(int i = 0; i < n; i++)
		cout << s[i];
	cout << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long curA = sc.nextLong();
        long curB = sc.nextLong();
        
        long a = 0, b = 0;
        for(int i = 1; i < n; i++) {
            a = sc.nextLong();
            b = sc.nextLong();
            if(a >= curA && b >= curB) {
                curA = a;
                curB = b;
            } else {
                long rate = Math.max((curA + a - 1) / a, (curB + b - 1) / b);
                curA = a * rate;
                curB = b * rate;
            }
        }
        
        System.out.println(curA + curB);
    }
}


Measured memory_bytes: 24404
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll N, K;
    cin >> N >> K;
    vl A(N);
    rep(i, N) cin >> A[i];

    ll ok = *max_element(all(A)), ng = 0;
    while(ok-ng>1){
        ll mid = (ok + ng) / 2, cnt = 0;
        rep(i, N){
            cnt += (A[i] - 1) / mid;
        }
        (cnt <= K ? ok : ng) = mid;
    }

    cout << ok << endl;
}

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

int main() {
  int N, Q;
  cin >> N >> Q;
  using P = pair<int, int>;
  using PP = pair<P, int>;
  set<PP> st;
  set<int> run;
  rep(i, 0, N) {
    int S, T, X;
    cin >> S >> T >> X;
    st.insert(PP(P(S - X, X), 1));
    st.insert(PP(P(T - X, X), 0));
  }
  rep(i, 0, Q) {
    int D; cin >> D;
    while(!st.empty() && D >= (*st.begin()).first.first) {
      if((*st.begin()).second) run.insert((*st.begin()).first.second);
      else run.erase(run.find((*st.begin()).first.second));
      st.erase(st.begin());
      if(st.empty()) break;
    }
    if(run.empty()) cout << -1 << endl;
    else cout << *run.begin() << endl;
  }
  return 0;
}


Measured memory_bytes: 26880
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1 << 30;

using namespace std;

using ll = long long;
using P = tuple<ll, ll>;
using iarr = valarray<int>;

int main()
{
    int N, M;
    cin >> N >> M;
    vector<P> ab(N),cd(M);
    for(int i = 0; i < N; ++i) cin >> get<0>(ab[i]) >> get<1>(ab[i]);
    for(int i = 0; i < M; ++i) cin >> get<0>(cd[i]) >> get<1>(cd[i]);

    for(int i = 0; i < N; ++i){
        ll min_dist = INFL;
        ll x = get<0>(ab[i]);
        ll y = get<1>(ab[i]);
        int index = -1;
        for(int j = 0; j < M; ++j){
            ll now = llabs(get<0>(cd[j]) - x) + llabs(get<1>(cd[j]) - y);
            if(min_dist > now){
                min_dist = now;
                index = j+1;
            }
        }
        cout << index << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
vector<int> fact(ll L){
  ll N = L;
  vector<int> res;
  for(ll i = 2; i * i <= N; i++)if(L % i == 0){
    int cnt = 0;
    while(L % i == 0){
      L /= i;
      cnt++;
    }
    res.push_back(cnt);
  }
  if(L != 1) res.push_back(1);
  return res;
}

int main(){
  ll L;
  while(cin >> L && L){
    if(L == 1){
      cout << 1 << endl;
      continue;
    }
    vector<int> v = fact(L);
    int dp[2] = {};
    dp[1] = v[0];
    for(int i = 1; i < v.size(); i++){
      dp[(i + 1) & 1] = dp[i & 1] * 2 * v[i] + v[i] + dp[i & 1];
    }
    cout << dp[v.size() & 1] + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
	int r, D, x;

	cin >> r >> D >> x;
	int ans = x;
	for (int i = 0; i < 10; i++) {
		ans = r * ans - D;
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 256