akhauriyash/Code-Regression huggingface dataset:
//     _
//   _/_\_
//   (O_o)
//  ~(   )~
//   (~~~)
//   /   \

#include <bits/stdc++.h>

#define left nadnlassad
#define right asdaslknd
#define y1 kjdajasjdsas
#define nxt accepted
#define prev why_would_you_call_when_you_are_high

#define pb push_back
#define mp make_pair
#define mt make_tuple

#define f first
#define s second

#define ll long long
#define ld long double
#define ull unsigned ll

#define hash_t pair<ll, ull>
#define pii pair<int, int>
#define uint unsigned int
#define puu pair<uint, uint>

#define sqr(x) ((x) * 1LL * (x))

#define vec vector<int>
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define endl "\n"
#define bits(x) __builtin_popcountll(x)
#define forn(i, s, t) for(int i = (int) s; i <= (int) t; i++)
#define form(i, t, s) for(int i = (int) t; i >= (int) s; i--)

using namespace std;

void rf() {
    #define fname "sparse"
    #ifdef SONY
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #else
        //freopen(fname".in", "r", stdin);
        //freopen(fname".out", "w", stdout);
    #endif //SONY
}

const int nx[8] = {2, -2, -2, 2, 1, 1, -1, -1};
const int ny[8] = {1, 1, -1, -1, 2, -2, -2, 2};
const int Nx[4] = {0, 0, -1, 1};
const int Ny[4] = {1, -1, 0, 0};

const ll LINF = (ll) 5e18;
const int INF = 1e9 + 7;

const int N = 6e5 + 1;
const int MAXN = 1e6 + N;
const double EPS = 1e-9, PI = 3.14159265359;

inline int get_int() {
    char x = getchar();
    int ret = 0;
    bool neg = 0;
    while (!('0' <= x && x <= '9')) {
        if (x == '-')
            neg = 1;
        x = getchar();
    }
    while ('0' <= x && x <= '9') {
        ret = ret * 10 + x - '0';
        x = getchar();
    }
    if (neg) ret *= -1;
    return ret;
}

string a, b;
int cnt[2][N];

int get(int t, int l, int r) {
    return cnt[t][r] - (l ? cnt[t][l - 1] : 0);
}

bool ok(int l1, int r1, int l2, int r2) {
    int a1 = get(0, l1, r1);
    a1 += (r1 - l1 + 1 - a1) * 2;
    int a2 = get(1, l2, r2);
    a2 += (r2 - l2 + 1 - a2) * 2;
    return a1 % 3 == a2 % 3;
}

int main() {
    srand(time(0));
    //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //rf();
    ld beg = clock();
    cin >> a >> b;
    forn (i, 0, sz(a) - 1) {
        cnt[0][i] += (a[i] == 'A');
        cnt[0][i + 1] = cnt[0][i];
    }
    forn (i, 0, sz(b) - 1) {
        cnt[1][i] += (b[i] == 'A');
        cnt[1][i + 1] = cnt[1][i];
    }
    int q;
    cin >> q;
    while (q--) {
        int l1, l2, r1, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        --l1, --r1, --l2, --r2;
        cout << (ok(l1, r1, l2, r2) ? "YES" : "NO") << endl;
    }
    #ifdef SONY
        fprintf(stderr, "\n%.6f", (double) (clock() - beg) / CLOCKS_PER_SEC);
    #endif //SONY
    return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <vector>

using namespace std;

int main(){
  unsigned long long N;
  vector<unsigned long long> vec(5,0);
  cin>>N;
  for(int i=0;i<5;i++) cin>>vec[i];
  
  unsigned long long mnum=0;
  for(int i=0;i<5;i++){
    if(mnum>vec[i]||mnum<1)mnum=vec[i];
  }

  unsigned long long num=N/mnum+(N%mnum!=0?1:0);; 
  cout<<5+num-1<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
using namespace std;
int main(){
    char al; cin >> al;
    int d = al - 'A';
    if(d>= 0 && d<= 25){cout << 'A' << endl;}
    else{cout << 'a' << endl;}
    return 0;
}

Measured memory_bytes: 3636
fun main() {
    val limit = 1000000
    val era = BooleanArray(limit + 1)
    val primes = ArrayList<Int>()
    var d = 2

    // a1 a2 a3 a4 ai ai+1, ...  an-1, an
    // Ai <= Ai+1
    // Ai = set(p0, p1, ... pk)
    // Ai 가 Aj 에 의해 divide 된다는 것은 Aj 를 소인수분해했을때 나오는 모든 소수들을 Ai 가 가지고 있어야한다.
    // 그리고 Aj 의 각 소수의 지수들은 Ai 의 그 소수의 지수들보다는 작거나 같아야 한다.
    // Ai 가 Divisible 되는지 확인하는 방법은, Ai 보다 작은 수들 중에서 위 조건을 만족하는 애들을 찾는 것이다.
    // 일단 중복된 수들은 Non - Divisible 이다. 그리고, 숫자 1이 나오면 1 보다 큰 모든 수들은 전부 Non-Divisible 이다.
    // 100만 + 50만 + 33 + 20 + 14만 + 9만 + 7


    while (d <= limit) {
        if(era[d]) {
            ++d
            continue
        }
        primes.add(d)
        var k = d
        while (k <= limit) {
            era[k] = true
            k += d
        }
        ++d
    }

    var tt = 0L
    for(p in primes) {
        tt += limit / p
    }

    val n = readLine()!!.toInt()
    val arr = readLine()!!.split(" ").map { it.toInt() }.sorted().toIntArray()
    val checked = IntArray(limit + 1) //0 : empty, 1 : visit, 2: divisible

    for(i in arr.indices) {
        val v = arr[i]
        if(checked[v] == 1) {
            checked[v] = 2
            continue
        }
        if(checked[v] == 2) {
            continue
        }
        checked[v] = 1
        var k = 2
        while(v * k <= limit) {
            checked[v*k] = 2
            ++k
        }
    }
    var ans = 0
    for(i in arr.indices) {
        if(checked[arr[i]] == 1)
            ++ans
    }
    print(ans)
}


Measured memory_bytes: 68056
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] numbers = new int[n];
		for(int i = 0; i < n; i++) {
			numbers[i] = in.nextInt();
		}
		int tempMin = numbers[0];
		int count = 1;
		for(int i = 1; i < n; i++) {
			if(numbers[i] < tempMin) {
				count++;
				tempMin = numbers[i];
			}
		}
		System.out.println(count);	
	}
}


Measured memory_bytes: 84008
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    int sum = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> A.at(i);
        sum += A.at(i);
    }
    
    int res = 0;
    for (int i = 0; i < N; i++)
    {
        if (A.at(i) >= (double)sum / (4 * M)) res++;
    }
    if (res >= M) cout << "Yes" << endl;
    else cout << "No" << endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main(){
  string s;
  string t;
  int q;
  cin >> s;
  cin >> q;
  rep(i,q){
    int ty;
    cin >>ty;
    if(ty==1){
      swap(s,t);
    }
    else{
      int tz;char c;
      cin >> tz >> c;
      if(tz==1){
        t +=c;
      }
      else {
        s +=c;
      }
    }
  }
  reverse(t.begin(),t.end());
  t+=s;
  cout << t << endl;
  return 0;
}

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

int main() {
	int i,j,s,n,m[100],a[100],b[100];
    while(cin >> n && n>0) {
		for (i=0;i<n;i++) cin >> m[i] >> a[i] >> b[i];
		for (i=0;i<n;i++) {
		     for (j=0,s=0;j<n;j++) if (a[i]>=a[j] && a[i]<b[j]) s+=m[j];
		     if (s>150) break;
	     }
	 if (s>150) cout << "NG"; else cout << "OK";
	 cout << endl;  	
	}
	return 0;
}

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

string in;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>in;
    cout<<in[0]<<in.size()-2<<in[in.size()-1];
    return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) int((x).size())
#define OUT(x) cout << (x) << endl
typedef long long ll;
typedef vector<int> V;
typedef vector<vector<int>> VV;
typedef pair<int, int> P;
typedef map<string, int> M;
typedef unordered_map<int, int> HM;
typedef set<int> S;
typedef multiset<int> MS;
typedef queue<int> Q;

int main(){
    string s; cin>>s;
    char pre = s[0];
    for(int i=1; i<s.size(); i++){
        if(s[i] == pre){
            cout << "Bad" << endl;
            return 0;
        }
        pre = s[i];
    }
    cout << "Good" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;
    vector<ll> p(A), q(B), r(C);
    for (int i = 0; i < A; i++) cin >> p[i];
    for (int i = 0; i < B; i++) cin >> q[i];
    for (int i = 0; i < C; i++) cin >> r[i];
    sort(p.begin(), p.end(), greater<ll>());
    sort(q.begin(), q.end(), greater<ll>());
    sort(r.begin(), r.end(), greater<ll>());
    int i = X - 1, j = Y - 1;
    for (int k = 0; k < C; k++) {
        if (i >= 0 && j >= 0) {
            if (p[i] <= q[j]) {
                if (r[k] > p[i]) {
                    p[i] = r[k];
                    i--;
                }
            }
            else{
                if (r[k] > q[j]) {
                    q[j] = r[k];
                    j--;
                }
            }
        }
        else if (i >= 0) {
            if (r[k] > p[i]) {
                p[i] = r[k];
                i--;
            }
        }
        else if (j >= 0) {
            if (r[k] > q[j]) {
                q[j] = r[k];
                j--;
            }
        }
    }
    ll ans = accumulate(p.begin(), p.begin() + X, 0LL) + accumulate(q.begin(), q.begin() + Y, 0LL);
    cout << ans << '\n';
}


Measured memory_bytes: 2560
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

l = [a,b,c,d,e]
l2 = sorted(l)
if k >= l2[4]-l2[0]:
    print('Yay!')
else:
    print(':(')


Measured memory_bytes: 3060
#include<stdio.h>


int main(void){
	int n,m = 0,nx = 0,i;
	char s[128];
	scanf("%d%s",&n,s);
	for(i = 0;i < n;i++){
		if(s[i] == 'I'){nx++;}else{nx--;}
		if(m < nx){m = nx;}
	}
	printf("%d\n",m);
	return 0;
}

Measured memory_bytes: 128
import math
a,b,x =map(int,input().split())

if x <(a*a*b)/2:
  hen=(x*2)/(a*b)
  print(math.degrees(math.atan(b/hen)))
  
  
else:
  taiseki=a*a*b-x
  hen=(taiseki*2)/(a*a)
  print(math.degrees(math.atan(hen/a)))



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

int main() {
  
  int n;
  cin >> n;
  
  for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++) {
      if(i*j == n) {
        cout << "Yes";
        return 0;
      }
    }
  }
  
  cout << "No";
  
}


Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
	std::string str;
	cin >> str;

	if (str[0] == str[1] && str[1] == str[2])
		cout << "No" << endl;
	else
		cout << "Yes" << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
void read(int &x){
	char c=getchar();
	int f=1;
	x=0;
	while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
	x*=f;
}
priority_queue<int> q;
signed main(){
	int i,j,k,m,n;
	read(n);read(m);
	for(register int i=1;i<=n;i++){
		int x;
		read(x);
		q.push(x);
	}
	for(register int i=1;i<=m;i++){
		int x=q.top();
		q.pop();
		x/=2;
		q.push(x);
	}
	int ans=0;
	while(!q.empty()){
		int x=q.top();
		q.pop();
		ans+=x;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1400
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		char[] a = sc.next().toCharArray();
		char[] b = sc.next().toCharArray();
		char[] c = sc.next().toCharArray();
		int count = 0;
		for(int i = 0; i < n; i ++) {
			if(a[i] == b[i]) {
				if(a[i] == c[i]) {

				}else{
					count ++;
				}
			}else{
				if(a[i] == c[i]) {
					count ++;
				}else if(b[i] == c[i]) {
					count ++;
				}else {
					count += 2;
				}
			}
		}
		System.out.println(count);

	}
}

Measured memory_bytes: 20948
#include <bits/stdc++.h>
#define reg register
#define MAXN 2505
#define MAXE 5005

using namespace std;

const int mod = 1e9 + 7;
int N, M, P;
int head[MAXN], to[MAXE], nex[MAXE], val[MAXE], tote;
int dist[MAXN], rec[MAXN];
bool vis[MAXN], able[MAXN];
struct edges {
    int u, v, c;
}e[MAXE];

inline int Rd() {
    int xx=0,flag2=1;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')
		ch=getchar();
	if(ch=='-'){
		flag2=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		xx=xx*10+ch-'0';
		ch=getchar();
	}
	return flag2*xx;
}
inline void add_edge(int u, int v, int c) {
    nex[++tote] = head[u], to[tote] = v, val[tote] = c, head[u] = tote;
    return;
}

void dfs(int str) {
    able[str] = vis[str] = true;
    for(int i = head[str]; i; i = nex[i])
        if(!vis[to[i]])
            dfs(to[i]);
    return;
}
void clear() {
    tote = 0;
    memset(head, 0, sizeof head);
    memset(vis, 0, sizeof vis);
    memset(nex, 0, sizeof nex);
    memset(to, 0, sizeof to);
    return;
}
void SPFA() {
    queue<int> que; que.push(1);
    for(reg int i = 2; i <= N; ++i) dist[i] = -mod;
    while(!que.empty()) {
        int s = que.front(); que.pop(), vis[s] = false;
        if(!able[s]) continue;
        for(int i = head[s]; i; i = nex[i]) {
            if(dist[to[i]] < dist[s] + val[i]) {
                dist[to[i]] = dist[s] + val[i];
                if(!vis[to[i]]) {
                    vis[to[i]] = true, ++rec[to[i]];
                    if(rec[to[i]] >= N) {
                        if(able[to[i]]) {
                            puts("-1");
                            exit(0);
                        }
                        continue;
                    }
                    que.push(to[i]);
                }
            }
        }
    }
    return;
}
int main() {
    N = Rd(), M = Rd(), P = Rd();
    for(reg int i = 1; i <= M; ++i) {
        e[i].u = Rd(), e[i].v = Rd(), e[i].c = Rd();
        add_edge(e[i].v, e[i].u, 0);
    }
    dfs(N);
    clear();
    for(reg int i = 1; i <= M; ++i)
        add_edge(e[i].u, e[i].v, e[i].c - P);
    SPFA();
    if(dist[N] < 0) dist[N] = 0;
    cout << dist[N] << endl;
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const int INF=1000000001;
const double PI=3.141592653589;


int main(){
  string s; cin>>s;
  if(s[0]==s[1]&&s[0]==s[2])
  puts("Yes");
  else if(s[1]==s[2]&&s[1]==s[3])
  puts("Yes");
  else
  puts("No");


  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 6100000;
const int K = 19;
const int mod = 998244353;
int z[N], a[N], b[N];
void zcalc(vector < int > a){
    int l = 0;
    int r = 0;
    int n = a.size();
    for (int i = 1; i < n; i++){
        if (i <= r){
            z[i] = min(z[i - l], r - i + 1);
        }
        while(i + z[i] < n && a[i + z[i]] == a[z[i]]){
                z[i]++;
            }
        if (i + z[i] - 1 > r){
            l = i;
            r = i + z[i] - 1;
        }
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    for (int i = 0; i < n; i++){
        cin >> b[i];
    }
    vector < int > c;
    for (int i = 0; i < n; i++){
        c.pb(b[i] ^ b[(i + 1) % n]);
    }
    c.pb(-1);
    for (int i = 0; i < n + n; i++){
        c.pb(a[i % n] ^ a[(i + 1) % n]);
    }
    zcalc(c);
    vector < pair < int, int > > ans;
    for (int i = n + 1; i < n + n + 1; i++){
        if (z[i] == n){
            ans.pb({i - n - 1, b[0] ^ a[i - n - 1]});
        }
    }
    for (auto i: ans){
        cout << i.F << " " << i.S << endl;
    }
}


Measured memory_bytes: 28312
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ve vector
#define chmin(x,y) x = min(x,y)

int main(){
    int n;
    string s;
    cin >> n >> s;
    ve<int> e(n+1),w(n+1);
    e[0] = 0;
    w[0] = 0;
    rep(i,n){
        if(s[i] == 'E')e[i+1]++;
        else w[i+1]++;
        e[i+1] += e[i];
        w[i+1] += w[i];
    }
    int ans = 2e9;
    rep(i,n){
        ans = min(ans,w[i]-w[0] + e[n]-e[i+1]);
    }
    cout << ans << endl;
    return 0;
}


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


int main() {
    char ans[4];
    for (int i = 0; i < 9;i++){
        char op;
        cin>>op;
        if(i==0)ans[0]=op;
        if(i==4)ans[1]=op;
        if(i==8)ans[2]=op;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (((a)%mod) * ((b)%mod)) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// typedef
typedef complex<double> Point;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;
const int mod = 1e9+7;
// int sum = accumulate(a, a+n, 0LL);
// int mx = max_element(a, a+n);
// int mn = min_element(a, a+n);
// int cnt = count(a, a+n, k);

int N,X;

int l[110];

int cnt;

int ans=1;

signed main()
{
    cin >> N >> X;

    rep(i,N)cin >> l[i];

    rep(i,N)
    {
        

        cnt+=l[i];

        if(cnt<=X)ans++;
    }

    cout << ans<< endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
int i,a,b,c,m;
scanf("%d %d %d",&a,&b,&c);
for(i=1;i<=10;++i){
		if(a>b){
			m=a,a=b,b=m;
		}
		if(b>c){
			m=b,b=c,c=m;
		}
	}
printf("%d %d %d\n" , a,b,c);
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
using namespace std;


int main(void)
{
	int N, K;
	lli S;
	cin >> N >> K >> S;
	rep(i, 0, K)cout << S << " ";
	//lli S_n = (S >= 9223372036854775807 ? (S - 1) : (S + 1));
	rep(i, 0, N - K)cout << S/2+100 << " ";
	//rep(i, 0, N - K)cout << 2*S << " ";
	cout << endl;

	return 0;
}

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

const int maxn = 200005;

int n, l, r;
int a[maxn], pos[maxn];
long long ans;
set < int > border;
set < int > :: iterator j;

signed main () {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		pos[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		l = 0, r = n + 1;
		j = border.upper_bound(pos[i]);
		if (j != border.end())
			r = *j;
		if (j != border.begin())
			l = *prev(j);
		ans += ((long long) i) * ((long long) pos[i] - l) * ((long long) r - pos[i]);
		border.insert(pos[i]);
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 14720
#include<bits/stdc++.h>
using namespace std;
long long n, k, a[100001], f[100001], rt;
int main()
{
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=1e9;
    }
    f[1]=0;
    //a[0]=-1e9;
    for(long long i=2;i<=n;i++)
    {
        if(i<=k)
        {
            for(int j=1;j<i;j++)
                f[i]=min(f[i], f[i-j]+abs(a[i]-a[i-j]));
        }
        else{
            for(int j=1;j<=k;j++)
                f[i]=min(f[i], f[i-j]+abs(a[i]-a[i-j]));
        }
    }
    cout<<f[n];
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    string a, b, c;
    cin >> a >> b >> c;
    string ans = "YES";
    if (a.back()!=b[0] || b.back()!=c[0]) ans = "NO";
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#include <cstring>
#include <iostream>
#define pie acos(-1)
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sl(a) scanf("%lld",&a)
#define sll(a,b) scanf("%lld %lld",&a,&b)
#define slll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define ss(st) scanf("%s",st)
#define sch(ch) scanf("%ch",&ch)
#define ps(a) printf("%s",a)
#define newLine() printf("\n")
#define pi(a) printf("%d",a)
#define pii(a,b) printf("%d %d",a,b)
#define piii(a,b,c) printf("%d %d %d",a,b,c)
#define pl(a) printf("%lld",a)
#define pll(a,b) printf("%lld %lld",a,b)
#define plll(a,b,c) printf("%lld %lld %lld",a,b,c)
#define pd(a) printf("%lf",a)
#define pdd(a,b) printf("%lf %lf",a,b)
#define pddd(a,b,c) printf("%lf %lf %lf",a,b,c)
#define pch(c) printf("%ch",c)
#define debug1(str,a) printf("%s=%d\n",str,a)
#define debug2(str1,str2,a,b) printf("%s=%d %s=%d\n",str1,a,str2,b)
#define debug3(str1,str2,str3,a,b,c) printf("%s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c)
#define debug4(str1,str2,str3,str4,a,b,c,d) printf("%s=%d %s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c,str4,d)
#define for0(i,n) for(i=0;i<n;i++)
#define for1(i,n) for(i=1;i<=n;i++)
#define forab(i,a,b) for(i=a;i<=b;i++)
#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define NL puts("")
#define sd(a) scanf("%lf",&a)
#define sdd(a,b) scanf("%lf %lf",&a,&b)
#define sddd(a,b,c) scanf("%lf %lf %lf",&a,&b,&c)
#define SP printf(" ")
#define LL long long int
#define ULL unsigned long long int
#define N 1000007
#define MOD 100000009
#define pub(x) push_back(x)
#define pob(x) pop_back(x)
#define mem(ara,value) memset(ara,value,sizeof(ara))
#define INF INT_MAX
#define eps 1e-8
#define checkbit(n, pos) (n & (1<<pos))
#define setbit(n, pos) (n | (1<<pos))
#define para(a,b,ara)\
for(int i=a;i<=b;i++){\
    if(i!=0){printf(" ");}\
    printf("%d",ara[i]);\
}\
printf("\n");
#define pvec(vec)\
for(int i=0;i<vec.size();i++){\
    if(i!=0){printf(" ");}\
    printf("%d",vec[i]);\
}\
printf("\n");
#define ppara(n,m,ara)\
for(int i=0;i<n;i++){\
    for(int j=0;j<m;j++){\
        if(j!=0){printf(" ");}\
        printf("%d",ara[i][j]);\
    }\
    printf("\n");\
}
#define ppvec(n,vec)\
for(int i=0;i<n;i++){\
    for(int j=0;j<vec[i].size();j++){\
        if(j!=0){printf(" ");}\
        printf("%d",vec[i][j]);\
    }\
    printf("\n");\
}
#define sara(a,b,ara)\
for(int i=a;i<=b;i++){\
    scanf("%d",&ara[i]);\
}
using namespace std;
int n,ara[2010];
bitset <2010*2010> dp[2];
int sum=0;
void input(){
    int i,j,ans;
    si(n);
    for0(i,n){si(ara[i]);sum+=ara[i];}
    dp[0].set(0);
    for1(i,n){
        dp[i&1]=dp[(i-1)&1]|(dp[(i-1)&1]<<ara[i-1]);
    }
    ans=0;
    for(i=(sum+1)/2;i<2005*2005;i++){
        if(dp[n&1][i]){
            ans=i;
            break;
        }
    }
    pi(ans);NL;
}
int main(){
    input();
    return 0;
}



Measured memory_bytes: 2688
from operator import itemgetter

def main():

    N = int(input())
    if 0 > N or N > 100:
        print("input N error")
        exit()
        
    answer = []
    for i in range(N):
        s, p = input().split()
        answer.append([s, -int(p), i+1])

    answer.sort(key=itemgetter(0,1))
    for i in range(len(answer)):
        print(answer[i][2])
        
        
if __name__ == '__main__':

    main()

    


Measured memory_bytes: 3060
n,k=map(int,input().split(" "))
if n<k:
    print(0)
else:
    a=[1,0]
    for i in range(n):
        a=[0]+[a[i-1]+i*a[i] for i in range(1,len(a))]+[0]
    print(a[k]%(10**9+7))


Measured memory_bytes: 7020
import itertools
import re

n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))

n_list = list(range(1, n + 1))

conv =[]
for v in itertools.permutations(n_list, n):
    conv.append(v)

for i, j in enumerate(conv):
    if p == j:
        p_ind = i + 1

for i, j in enumerate(conv):
    if q == j:
        q_ind = i + 1

print(abs(p_ind - q_ind))

Measured memory_bytes: 8172
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, int>> p(m);
	rep(i, m) {
		int P, y;
		cin >> P >> y;
		
		p[i] = make_tuple(y, P, i);
	}
	sort(all(p));
	vector<vector<int>> id(n+1);
	vector<tuple<int, int, int>> ans(m);
	rep(i, m) {
		int P = get<1>(p[i]);
		int x = id[P].size() + 1;
		id[P].push_back(x);
		ans[i] = make_tuple(get<2>(p[i]), P, x);
	}
	sort(all(ans));
	rep(i, m) {
		int P = get<1>(ans[i]);
		int x = get<2>(ans[i]);
		printf("%06d%06d\n", P, x);
	}
	
	
	return 0;
}

Measured memory_bytes: 9344
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

#define fbo find_by_order
#define ook order_of_key
#define fi first
#define se second
#define long long long
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// void initiate_random() { mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count()); }

// /mnt/c/Users/vince/Desktop/POST-IOI/Codeforces/Regular/670

int main()
{
	// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// freopen("input.in", "r", stdin);

	long a, v;
	long b, w;
	long t;
	scanf("%lld %lld %lld %lld %lld", &a, &v, &b, &w, &t);

	long dif = abs(b-a);
	long speed = v-w;
	if(speed <= 0) printf("NO\n");
	else if(speed*t >= dif) printf("YES\n");
	else printf("NO\n");

}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  map<int, int> mp;
  REP(i,3){
    int a,b; cin >> a >> b;
    mp[a]++, mp[b]++;
  }
  bool flag = true;
  for(auto p: mp){
    if(p.second==3) flag = false;
  }
  cout << (flag ? "YES\n" : "NO\n");
  return 0;
}


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

using namespace std;

int main() {
    vector<int> q(5);
    for (int i = 0; i < 5; ++i)
        cin >> q[i];
    int k;
    cin >> k;
    bool flag = false;
    for (int i = 0; i < 5; ++i) {
        for (int j = i; j < 5; ++j) {
            if (abs(q[i] - q[j]) > k)
                flag = true;
        }
    }
    if (flag == true)
        cout << ":(";
    else
        cout << "Yay!";
}

Measured memory_bytes: 256
S2 = input()
T = input()

N = len(S2)


def check(S, T):
    for i in range(len(S)):
        if S[i] == '?' or S[i] == T[i]:
            continue
        else:
            return False
    return True


S = 'UNRESTORABLE'
if len(T) <= N:
    C = []
    for i in range(N - len(T) + 1):
        j = i + len(T)
        if (S2[i] == T[0] or S2[i] == '?') and check(S2[i:j], T):
            S = list(S2)
            S[i:j] = list(T)
            S = ''.join(S).replace('?', 'a')
            C.append(S)
    if len(C) > 0:
        S = sorted(C)[0]
print(S)


Measured memory_bytes: 3064
import java.util.*;
class Main{
    static Scanner sc=new Scanner(System.in);
    public static void main(String[] args){
        int N = sc.nextInt();
      long n = N;
        long ans = 0;
        for(long i=1;i<=N;i++){
        if(((i%3)!=0)&&((i%5)!=0))
        ans= ans+i;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 35756
until(s=gets.gsub(/\d+/){|k|?1*k.hex})[?#]
n=1+s.index(?/)
eval"s[n*c-n+e-1]=?1;s[n*g-n+i-1]=?bdfh".tr('c-i',gets)
$><<s.gsub(/1+/,&:size)
end

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int h[200000];
int main(){
	int n,K;cin>>n>>K;
	int cnt=0;
	rep(i,n){
		cin>>h[i];
		if(h[i]>=K)cnt++;
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 640
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(10**6)

def main():
    H, W, A, B = map(int, input().split())
    ans = 0
    for i in range(1, H - A + 1):
        ans += comb(i + B - 2, i - 1) * comb(H - i + W - B - 1, H - i)
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 212396
#include <iostream>
#include <algorithm>
#include<stdio.h>
#include<map>
#include<utility>
using namespace std;
struct unionfind{
  int par[200010];
  int rank[200010];
  unionfind(int n){
    init(n);
  }
  void init(int n){
    for(int i=0;i<n;i++){
      par[i]=i;
      rank[i]=0;
    }
  }
  int root(int x) {
    if (par[x] == x) {
      return x;
    }
    else {
      return par[x] = root(par[x]);
    }
  }
  bool same(int x,int y) {
    return root(x) == root(y);
  }
  void unite(int x,int y) {
    x=root(x);
    y=root(y);
    if(x==y){
      return;
    }
    if(rank[x]<rank[y]){
      par[x]=y;
    }
    else{
      par[y]=x;
      if(rank[x]==rank[y]){
        rank[x]++;
      }
    }
  }
};
int main(){
  int i,n,k,l,p,q;
  pair<int,int> p1;
  map<pair<int,int>,int> store;
  scanf("%d %d %d\n",&n,&k,&l);
  unionfind tree1(n);
  unionfind tree2(n);
  for(i=0;i<k;i++){
    scanf("%d %d\n",&p,&q);
    tree1.unite(p,q);
  }
  for(i=0;i<l;i++){
    scanf("%d %d\n",&p,&q);
    tree2.unite(p,q);
  }
  for(i=1;i<=n;i++){
    p1.first=tree1.root(i);
    p1.second=tree2.root(i);
    store[p1]++;
  }
  for(i=1;i<=n;i++){
    p1.first=tree1.root(i);
    p1.second=tree2.root(i);
    if(i==1){
       printf("%d",store[p1]);
    }
    else{
    printf(" %d",store[p1]);
    }
  }
  printf("\n");
  return 0;
}

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

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

int main(){
    int i,k;
    rep(i,9){
        rep(k,9){
            printf("%dx%d=%d\n",i+1,k+1,(i+1)*(k+1));
        }
    }
    return 0;
}

Measured memory_bytes: 3028
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int r[101];
int s[101][3];
int gp[101][3];
int sum[101];

bool C(int v,int x){
	s[0][v]+=x;
	memset(sum,0,sizeof(sum));
	for(int i=0;i<3;i++){
		for(int j=0;j<n;j++){
			int cnt=0;
			for(int k=0;k<n;k++){
				if(j==k)continue;
				if(s[j][i]<s[k][i])cnt++;
			}
			sum[j]+=r[cnt];
		}
	}
	s[0][v]-=x;
	int cnt=0;
	for(int i=1;i<n;i++){
		if(sum[0]<sum[i])cnt++;
	}
	return (cnt<8);
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&r[i]);
	}
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&s[i][0],&s[i][1],&s[i][2]);
	}
	int res=101;
	for(int i=0;i<3;i++){
		int l=-1,r2=101;
		while(r2-l>1){
			int mid=(l+r2)/2;
			if(C(i,mid))r2=mid;
			else l=mid;
		}
		res=min(res,r2);
	}
	if(res==101)printf("Saiko\n");
	else printf("%d\n",res);
	return 0;
}

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

using namespace std;

typedef long long ll;

int main(){
  string a,b,c;
  cin>>a>>b>>c;
  ll al=a.size();
  ll ai=0;
  ll bl=b.size();
  ll bi=0;
  ll cl=c.size();
  ll ci=0;
  ll turn=0;
  bool gameEnded=false;
  while(!gameEnded){
    if(turn==0){
      if(ai==al){
        gameEnded=true;
      }else{
      	turn=a[ai]-'a';
      	ai++;
      }
    }else if(turn==1){
      if(bi==bl){
        gameEnded=true;
      }else{
      	turn=b[bi]-'a';
      	bi++;
      }
    }else{
      if(ci==cl){
        gameEnded=true;
      }else{
      	turn=c[ci]-'a';
      	ci++;
      }
    }
  }
  
  if(turn==0){
  	cout<<"A"<<endl;
  }else if(turn==1){
  	cout<<"B"<<endl;
  }else{
    cout<<"C"<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<int> > G;
typedef pair<int, int> P;

int main(){
	int n; scanf("%d", &n);
	G.resize(n);
	vector<P> vec;
	for(int i = 0; i < n - 1; i++){
		int a, b; scanf("%d %d", &a, &b); 
		--a; --b;
		G[a].push_back(b); G[b].push_back(a);
		vec.push_back(P(a, b));
	}
	vector<int> used(n, 0), color(n);
	int MAX_COLOR = 0;
	queue<int> que;
	used[0] = 1; que.push(0);
	map<P, int> MAP;
	while(que.size()){
		int now = que.front(); que.pop();
		int num = 1;
		MAX_COLOR = max(MAX_COLOR, int(G[now].size()));
		for(auto next : G[now]){
			if(used[next]) continue;
			if(color[now] == num) num++;
			color[next] = num;
			MAP[P(now, next)] = num;
			MAP[P(next, now)] = num;
			num++;
			used[next] = 1;
			que.push(next);
		}
	}
	printf("%d\n", MAX_COLOR);
	for(auto value : vec) printf("%d\n", MAP[value]);
}

Measured memory_bytes: 22856
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e13;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  cout << setprecision(10) << fixed;

  ll xs, ys, xt, yt;
  cin >> xs >> ys >> xt >> yt;
  vector<triple> t; // <x,y,r>
  t.emplace_back(xs, ys, 0);
  t.emplace_back(xt, yt, 0);
  ll n;
  cin >> n;
  rep(i, n) {
    ll x, y, r;
    cin >> x >> y >> r;
    t.emplace_back(x, y, r);
  }

  // rep(i, n+2) {
  //   ll xi, yi, ri;
  //   tie(xi, yi, ri) = t[i];
  //   cout << xi << "," << yi << "," << ri << endl;
  // }

  // Here, calculate the distance.
  // dist[i][j] .. distance of i and j
  vector<vector<double>> dist(n+2, vector<double>(n+2));
  rep(i, n+2) rep(j, i) {
    ll xi, yi, ri;
    tie(xi, yi, ri) = t[i];
    ll xj, yj, rj;
    tie(xj, yj, rj) = t[j];
    double xdiff = abs(xi-xj);
    double ydiff = abs(yi-yj);
    double r = ri + rj;
    double d = sqrt(xdiff*xdiff + ydiff*ydiff) - r;
    // cout << "d: " << d << endl;
    chmax(dist[i][j], d);
    chmax(dist[j][i], d);
  }
  // printtree(dist);

  // Here, we do dijkstra
  vector<double> d(n+2, INF);
  d[0] = 0;
  priority_queue<pair<double, ll>, vector<pair<double, ll>>, greater<pair<double, ll>>> q; // <dist, index>
  q.push({ 0, 0 });
  while (!q.empty()) {
    auto p = q.top(); q.pop();
    double nd = p.first;
    ll v = p.second;
    if (nd > d[v]) { continue; } // already large
    rep(nv, n+2) {
      if (nv == v) { continue; } // skip same
      if (d[nv] > d[v] + dist[v][nv]) {
        d[nv] = d[v] + dist[v][nv];
        q.push(pair<double, ll>(d[nv], nv));
      }
    }
  }
  cout << d[1] << endl;
}


Measured memory_bytes: 13172
n, q = map(int, input().split())
s = str(input())
lr = [list(map(int, input().split())) for _ in range(q)]

cnt = 0
res = [0 for _ in range(len(s))]
for i in range(1, len(s)):
    if s[i - 1] == "A" and s[i] == "C":
        cnt += 1
    res[i] = cnt

for i in range(q):
    l, r = lr[i][0], lr[i][1]
    print(res[r - 1] - res[l - 1])


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

typedef long long int ll;
typedef double d;

#define tt int t; cin>>t; while(t--)
#define lo(i, a, b) for(int i=a; i<b; i++)
#define rlo(i, a) for(int i=a; i>0; i--)

#define be(a) a.begin(),a.end()
#define sz(x) x.size()

#define nl cout<<"\n";
#define sp cout<<" ";

#define su ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

int main()
{
    su;
    int k,a,b;
    cin>>k>>a>>b;
    lo(i,a,b+1)
    {
       if(i%k==0)
       {
          cout<<"OK";
          nl;
          return 0;
       }
    }
    cout<<"NG";
    nl;
    return 0;
}


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

signed main(){
	int N, M, i;
	scanf("%d%d", &N, &M);
	vector<int> H(N);
	for(i = 0; i < N; i++){
		scanf("%d", &H[i]);
	}
	vector<int> is_good(N, 1);
	for(i = 0; i < M; i++){
		int A, B;
		scanf("%d%d", &A, &B);
		A--;
		B--;
		if(H[A] <= H[B]){
			is_good[A] = 0;
		}
		if(H[B] <= H[A]){
			is_good[B] = 0;
		}
	}
	int ans = 0;
	for(i = 0; i < N; i++){
		ans += is_good[i];
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 4040
n = int(input())
n -= 1
b = list(map(int, input().split()))
ans = b[-1]
for i in range(n-1)[::-1]:
    if  b[i] <= b[i+1]:
        ans += b[i]
    else:
        ans += b[i+1]
print(ans+b[0])


Measured memory_bytes: 3060
#include <cstdio>
#include <cassert>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

#define fi first
#define se second

#define lf else if

namespace io
{
	const int maxb = 1 << 15;
	char b[maxb], *s = b, *t = b;
	bool Getchar(char &ch)
	{
		return ch = s == t && (t = (s = b) + fread(b, 1, maxb, stdin)) == b ? 0 : *s ++;
	}
	int Getint()
	{
		char ch;
		while (Getchar(ch) && (ch < '0' || ch > '9'));
		int s = ch - '0';
		while (Getchar(ch) && ch >= '0' && ch <= '9')
			s = s * 10 + ch - '0';
		return s;
	}
}

using io::Getint;

const int maxn = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inv2 = (Mod + 1) / 2;

void Chkadd(int &x, const int &y) { if ((x += y) >= Mod) x -= Mod; }
void Chksub(int &x, const int &y) { if ((x -= y) < 0) x += Mod; }

int Power(int a, int k)
{
	int x = 1;
	for (; k; k >>= 1)
	{
		if (k & 1) x = 1ll * x * a % Mod;
		a = 1ll * a * a % Mod;
	}
	return x;
}

int n;
int A[maxn], cnt[maxn], S;
PII D[maxn], tree[maxn], iD[maxn];

PII operator * (const PII &a, const int &b)
{
	return b ? PII(1ll * a.fi * b % Mod, a.se) : PII(a.fi, a.se + 1);
}

void operator += (PII &a, const PII &b)
{
	if (a.se < b.se) a = b;
	lf (a.se == b.se) Chkadd(a.fi, b.fi);
}

void BIT_init()
{
	for (int i = 1; i <= n; ++ i) tree[i] = PII(0, 0);
}

void Update(int x, PII del)
{
	for (; x <= n; x += x & -x) tree[x] += del;
}

PII Query(int x)
{
	PII res(0, 0);
	if (!x) return res;
	for (; x ; x -= x & -x) res += tree[x];
	return res;
}

int tr[maxn];

void Insert(int x)
{
	for (; x <= n; x += x & -x) ++ tr[x];
}

int Getsum(int x)
{
	if (!x) return 0;
	int res = 0;
	for (; x; x -= x & (-x)) res += tr[x];
	return res;
}

int main()
{
	n = Getint();
	for (int i = 1; i <= n; ++ i)
	{
		A[i] = Getint();
		++ cnt[A[i]];
	}
	for (int i = n; i; -- i) cnt[i] += cnt[i + 1];
	S = 1;
	for (int i = n; i; -- i)
	{
		cnt[i] -= n - i;
		if (cnt[i] <= 0) return puts("0"), 0;
		S = 1ll * S * cnt[i] % Mod;
	}
	D[0] = PII(1, 0);
	for (int i = 1; i <= n; ++ i)
	{
		D[i] = D[i - 1] * (1ll * (cnt[i] - 1) * Power(cnt[i], Mod - 2) % Mod);
		iD[i] = PII(Power(D[i].fi, Mod - 2), D[i].se);
	}
	
	int ans = 0;
	
	for (int i = 1; i <= n; ++ i)
	{
		int cur = A[i];
		PII res = Query(cur);
		assert(res.se <= D[cur].se);
		if (res.se == D[cur].se)
			Chkadd(ans, 1ll * D[cur].fi * res.fi % Mod);
		Update(cur, iD[cur]);
	}
	
	BIT_init();
	
	for (int i = n; i; -- i)
	{
		int cur = A[i];
		PII res = Query(cur - 1);
		assert(res.se <= D[cur].se);
		if (res.se == D[cur].se)
			Chksub(ans, 1ll * D[cur].fi * res.fi % Mod);
		Update(cur, iD[cur]);
		
		Chkadd(ans, 2ll * Getsum(cur - 1) % Mod);
		Insert(cur);
	}
	
	ans = 1ll * ans * S % Mod * inv2 % Mod;
	
	printf("%lld\n", ans);
	
	return 0;
}

Measured memory_bytes: 7168
def judge(s):
    ans = 0
    add_3 = s * 10 + 3
    if add_3 <= N:
        str_num = str(add_3)
        if str_num.count("3") and str_num.count("5") and str_num.count("7"):
            ans += 1
        ans += judge(add_3)
    add_5 = s * 10 + 5
    if add_5 <= N:
        str_num = str(add_5)
        if str_num.count("3") and str_num.count("5") and str_num.count("7"):
            ans += 1
        ans += judge(add_5)
    add_7 = s * 10 + 7
    if add_7 <= N:
        str_num = str(add_7)
        if str_num.count("3") and str_num.count("5") and str_num.count("7"):
            ans += 1
        ans += judge(add_7)
    return ans


N = int(input())

print(judge(0))


Measured memory_bytes: 43484
def solve
  n = gets.to_i
  arr = []
  cnt = 1
  (0..(n - 1)).each do |i|
    arr[i] = gets.chomp
  end

  sorted_arr = arr.sort
  target_str = sorted_arr[0]
  (1..(n - 1)).each do |i|
    if target_str != sorted_arr[i]
      target_str = sorted_arr[i]
      cnt += 1
    end
  end

  print cnt
end
solve

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

int main() {
  int A, B, num, a1, a2, a3, b1, b2, b3;
  cin >> A >> B;
  num = 0;
  a1 = A / 10000;
  b1 = B / 10000;
  for (int i = a1; i < (b1 + 1); i++) {
    for (int j = 0; j < (9 + 1); j++) {
      for (int k = 0; k < (9 + 1); k++) {
        int n;
        n = i * 10000 + j * 1000 + k * 100 + j * 10 + i;
        if (n < A) {
          continue;
        }
        if (n > B) {
          break;
        }
        num ++;
      }
    }
  }
  cout << num << endl;
}


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

int getmd(int a,int b,int c,int d){
    return abs(a-c)+abs(b-d);
}

int main(){
    int n,ans(0);
    cin >> n;
    int d[n];
    rep(i,n)    cin >> d[i];

    rep(i,n){
        for(int j=i+1;j<n;j++){
            ans += d[i]*d[j];
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    long long x=0,y=0;
    for(int i=n;i>=1+1;i--)
    {
        if(x==0&&a[i]==a[i-1])
        {
            x=a[i];
            i--;
        }
        else if(x!=0&&a[i]==a[i-1])
        {
            y=a[i];
            break;
        }
    }
    printf("%lld\n",x*y);
    return 0;
}


Measured memory_bytes: 640
n, u, v = map(int, input().split())
u, v = u-1, v-1

g = [[] for i in range(n)]

for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append(b)
  g[b].append(a)
  
  
dt = [-1]*n
da = [-1]*n

from collections import deque
def dfs(g, s, d_list):
  stack = deque()
  stack.append(s)
  d_list[s] = 0
  while stack:
    x = stack.pop()
    for new_x in g[x]:
      if d_list[new_x] == -1:
        stack.append(new_x)
        d_list[new_x] = d_list[x]+1
  return d_list

dt = dfs(g, u, dt)
da = dfs(g, v, da)

d = 0
for i in range(n):
  if dt[i] < da[i]:
    d = max(d, da[i])
    
print(d-1)

Measured memory_bytes: 61804
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 1000000007;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    string s, t;
    cin >> s;
    cin >> t;
    
    ll ans = 1;
    int now = -1; // -1 : 初期化、 0 : 縦積み、　1 : 横積み
    for(int i=0; i<N; i++)
    {
        // cout << i << ' ';
        if(s[i] == t[i])
        {
            if(now == -1) ans *= 3;
            else if(now == 0) ans *= 2;
            now = 0;
        }
        else
        {
            if(now == -1) ans *= 6;
            else if(now == 0) ans *= 2;
            else if(now == 1) ans *= 3;
            now = 1;
            i++;
        }
        ans %= mod;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL -1
using namespace std;
const int64_t MOD = 1e9 + 7;

int binarySearch(vector<int> v, int key) {
	int left, right, mid;
	left = 0;
	right = v.size();

	while (left < right) {
		mid = (left + right) / 2;

		if (key == v.at(mid)) {
			return 1;
		}
		else if (key < v.at(mid)) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}

	return 0;
}

int main() {
	int n;
	cin >> n;
	vector<int> S(n);
	for (int i = 0; i < n; i++) cin >> S.at(i);

	int q;
	cin >> q;
	vector<int> T(q);
	for (int i = 0; i < q; i++) cin >> T.at(i);

	int sum = 0;
	for (int i = 0; i < q; i++) {
		if (binarySearch(S, T.at(i))) sum++;
	}

	cout << sum << endl;
}



Measured memory_bytes: 3804
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
#include<deque>
#include<cassert>
using namespace std;
typedef long long ll;
typedef pair<ll,int> p;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;
const int INF = 1001001001;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) {
    cin >> a[i];
  }
  vector<int> ans(n);
  for (int i = n - 1; i >= 0; --i) {
    int s = 0;
    int next = i + 1;
    for(int j = 2 * next - 1; j < n; j += next) {
      s += ans[j];
    }
    // cout << s << endl;
    if(s % 2 != a[i]) ans[i] = 1; 
  }

  int cnt = 0;
  rep(i, n) cnt += ans[i];
  cout << cnt << endl;
  rep(i, n) if(ans[i] == 1) cout << i + 1 << " ";
  if(cnt != 0) cout << endl;
}

Measured memory_bytes: 2432
# -*- coding: utf-8 -*-
import numpy as np
import math

a, b, h, m = map(int, input().split())

ax = a * math.cos(math.pi / 6 * h + math.pi / 360 * m)
ay = a * math.sin(math.pi / 6 * h + math.pi / 360 * m)

bx = b * math.cos(math.pi / 30 * m)
by = b * math.sin(math.pi / 30 * m)

ans = math.sqrt((ax - bx) ** 2 + (ay - by) ** 2)

print(ans)

Measured memory_bytes: 27196