akhauriyash/Code-Regression huggingface dataset:
//$g++ -std=c++11 Template.cpp 

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

priority_queue<int> q_descending;
priority_queue<int, vector<int>, greater<int> > q_ascending;

int p[100];

int
main(void){  
  ios_base::sync_with_stdio(false);

  int n;
  cin >> n;

  REP(i, n) cin >> p[i];

  SORT(p, n);

  ll sum = 0LL;
  REP(i, n-1) sum += p[i];

  sum += p[n-1]/2;

  cout << sum <<endl;
  
  return 0;
}


Measured memory_bytes: 256
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
	InputStream is;
	PrintWriter out;
	String INPUT = "";

	void solve() {
		int n = ni();
		out.println(3 * n * n);
	}
	
	void run() throws Exception {
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);

		long s = System.currentTimeMillis();
		solve();
		out.flush();
		// tr(System.currentTimeMillis() - s + "ms");
	}

	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nd() {
		return Double.parseDouble(ns());
	}

	private char nc() {
		return (char) skip();
	}

	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
									// ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}

Measured memory_bytes: 23124
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int x = saori.saori_hayami();
		int a = saori.saori_hayami();
		if(x < a){
			System.out.println(0);
		} else {
			System.out.println(10);
		}
		
		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 23124
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    char c;
    cin >> c;
    string vow = "aiueo";
    REP(i, vow.size()){
        if(c == vow[i]){
            cout << "vowel" << "\n";
            return 0;
        }
    }

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


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define vi vector<int>
#define pb push_back
#define INF 999999999
//#define INF (1LL<<59)

int main(){
	int n;
	while(cin>>n&&n){
		vector<int> q(n);
		q[0]=0;
		int sumP=0;
		rep(i,n){
			int p;
			cin>>p;
			sumP+=p;
		}
		rep(i,n-1)cin>>q[i+1];
		
		sort(q.begin()+1,q.end(),greater<int>());
		rep(i,q.size()-1) q[i+1] += q[i];
		
		ll maxi = 0;
		rep(i,q.size()){
			ll price=0;
			price = (n-i) * (sumP+q[i]);
			maxi = max(maxi,price);
		}
		cout<<maxi<<endl;
	}
}

Measured memory_bytes: 3408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); 
#define test ll t; cin>>t; while(t--)
int main() {
	fast;
	int a,b,c;
	cin>>a>>b>>c;
	if(a+b+c<22)cout<<"win";
	else 
	cout<<"bust";
	return 0;
}

Measured memory_bytes: 256
Main = input => {
  input = input.split("\n");
  const tmp = input[0].split(" ");
  const n = Number(tmp[0]);
  const k = Number(tmp[1]);
  const h = input[1].split(" ").map(ht => Number(ht));
  
  var cnt = 0;
  h.forEach(ht => {
    if (ht >= k) {
      cnt++;
    }
  });
  
  console.log(cnt);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 16588
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 100001
#define rep(i, a, b) for(ll i=a; i<b; i++)
#define rer(i, a, b) for(ll i=a-1; i>=b; i--)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
double x, t;

signed main(){
    cin >> t >> x;
    cout << t / x << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

int main()
{
	int n;
	int buttons[200000];
	bool pushed[200000];
	
	cin >> n;
	
	REP(i,n){
		cin >> buttons[i];
	}
	REP(i,n){
		pushed[i] = false;
//		cout << buttons[i] << " " << pushed[i] << endl;
	}
	
	int now = 0;
	int next;
	
	REP(i,200000){
//		cout << i << endl;
		pushed[now] = true;
		next = buttons[now]-1;
//		cout << i << " now:" << now << " next:" << next << endl;
		if(next==1){
			cout << i+1 << endl;
			break;
		}
		if(pushed[next]){
			cout << "-1" << endl;
			break;
		}
		now = next;
	}
	
}


Measured memory_bytes: 768
A,B,C,X,Y = map(int, input().split())

if A+B >= 2*C:
    priceA = 2*C*max(X,Y)
    priceB = 2*C*min(X,Y)
    if X > Y:
        priceB += A * (X-Y)
    elif Y > X:
        priceB += B * (Y-X)

    print(min(priceA,priceB))

else:
    print(A*X+B*Y)


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long h;
  cin >> h;
  long long foo = floor(log2(h));
  cout << (long long)pow(2, foo + 1) - 1 << '\n';
  return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
#define el endl
#define INF 1e8
typedef long long ll;
typedef long double ld;

int main() {
    int a, b;
    cin >> a >> b;
    string x = "", y = "";
    rep(i, a){
        x += to_string(b);
    }
    rep(i, b){
        y += to_string(a);
    }
    
    if(x >= y){
        cout << y << endl;
    }else{
        cout << x << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
  vector<int> a(5);
  cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
  int min=10;
  int num;
  int change = 0;
  for(int i=0;i<5;i++){
    if(a[i]%10!=0&&a[i]%10<min){
      min = a[i]%10;
      num = i;
      change = 1;
    }
  }
  if(!change){
    num=100;
  }
  int ans=0;
  for(int j=0;j<5;j++){
    if(num==j||a[j]%10==0){
        ans+=a[j];
    }else{
        ans+=a[j]+(10-(a[j]%10));
    }
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
N, M = gets.split.map(&:to_i)
num = Array.new(M+1, 0)
N.times do
    as = gets.split.map(&:to_i)
    as.shift
    as.each do |a|
        num[a] += 1
    end
end
puts (1..M).count{|i| num[i] == N}

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

using namespace std;
int main(){
  map <int, int> a;
  int n;
  cin >> n;

  for(int i=0;i<n;i++){
    int x;
    cin >> x;
    //cout << x << endl;
    if(a.find(x)==a.end()){
      a[x]=1;
    }else{
	    a[x]+=1;
    }
  }

  int ans=0;
  for(auto n_count:a){
    if(n_count.second%2!=0)ans++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 4864
// C.

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

static const LL MOD = 1000000007;

int main(int argc, char *argv[])
{
	LL n, ans = 1;
	cin >> n;
	int f[1001] = {};
	for (int i = 2; i <= n; ++i) {
		if (!f[i]) {
			LL c = 0;
			for (int j = i; j <= n; j += i) {
				f[j] = 1;
				int k = j;
				while ((k % i) == 0) {
					k /= i;
					++c;
				}
			}
			ans = (ans * (c + 1)) % MOD;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
f=lambda:map(int,input().split())
H,W=f()
A=[[*f()] for _ in [0]*H]
B=[[*f()] for _ in [0]*H]
G=[[set() for i in [0]*W] for j in [0]*H]
G[0][0].add(0)
for h in range(H):
    for w in range(W):
        d=A[h][w]-B[h][w]
        for a in G[h][w]:
            if h!=H-1:
                G[h+1][w].add(abs(a+d))
                G[h+1][w].add(abs(a-d))
            if w!=W-1:
                G[h][w+1].add(abs(a+d))
                G[h][w+1].add(abs(a-d))
res=set()
d=A[H-1][W-1]-B[H-1][W-1]
for a in G[H-1][W-1]:
    res.add(abs(a+d))
    res.add(abs(a-d))
print(min(res))

Measured memory_bytes: 539788
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
int N,M;

ll re(int a){
    ll an = 1;
    while(1){
        an *= a;
        a--;
        if(a==0)break;
        an %=MOD;
    }
    return an;
}
void solve(){
    if(abs(N-M)>1){
        cout << 0 << endl;
        return;
    }
    ll ans = 0;
    if(N==M){
        ans = (re(N)*re(M)*2)%MOD;
        cout << ans << endl;
        return;
    }
    ans = (re(N)*re(M))%MOD;
    cout << ans << endl;
}
int main(){
    cin >> N >>M;
    solve();
    return 0;

}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int n,i,j,tmp;
	int d[100];
	
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&d[i]);
	}
	d[n]=1000;
	
	for(i=0;i<n;i++){
		for(j=0;j<n-i;j++){
			if(d[j]>d[j+1]){
				tmp=d[j];
				d[j]=d[j+1];
				d[j+1]=tmp;
			}
		}
	}
	
	tmp=0;
	j=0;
	for(i=0;i<n;i++){
		if(d[i]>tmp){
			j++;
			tmp=d[i];
		}
	}
	
	printf("%d\n",j);
	
	return 0;
}

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

public class Main {

    private static FastReader in = new FastReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final long MOD = (long) 1e9 + 7;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int k = in.nextInt();
        String s = in.next();

        out.println(s.length() > k ? s.substring(0, k) + "..." : s);
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream inputStream) {
            br = new BufferedReader(new
                    InputStreamReader(inputStream));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        // https://qiita.com/masakinpo/items/5f77f2a879578a85a0bb
        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 25392
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int MAX = 2e5+10, MAXL = 20;
ll n, res, a, b, c, d;
ll arr[200];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> a >> b >> c >> d;
	for (int i = a+1; i <= b; i++)
		arr[i] = 1;
	for (int i = c+1; i <= d; i++)
		arr[i] ++;
	for (int i= 1; i <= 100;i++)
		if (arr[i]==2)
			res++;
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm> 
#include <vector> 
#include <numeric> 
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

int lng(int a,int b){
    if(a%b==0){
        return b;
    }else{
        return lng(b,a%b);
    }
}


int main(void){
    // Your code here!
    vector<long long int> v;
    int n;
    int inp;
    long long int ans;
    cin >> n;
    rep(i,n){
        cin >> inp;
        v.push_back((long long int)inp);
    }
    int count = 0;
    rep(i,n){
        if(v[i] < 0){
            count++;
        }
    }
    rep(i,n){
        v[i] = abs(v[i]);
    }
    long long int total = std::accumulate(v.begin(), v.end(), 0LL);
    if(count%2){
        ans = total- *std::min_element(v.begin(), v.end())*2;
    }else{
        ans = total;
    }
        
    
    cout << ans << endl;
}


Measured memory_bytes: 1400
s = int(input())
MOD = 10**9 + 7
memo = [[0]*(s+1) for _ in range(s//3 + 1)]
flag = True
if s <= 2: flag = False

if flag:
    memo[1] = [0] * 3 + [1] * (s-2)

    for i in range(2, s//3 + 1):
        for j in range(3*i-3, s+1):
            memo[i][j] = memo[i][j-1] + memo[i-1][j-3]

    ans = 0
    for i in range(s//3 + 1):
        ans += memo[i][s]
        ans %= MOD
    print(ans) 
else: print(0)            

Measured memory_bytes: 89116
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    int n,tmp,num=0;
    cin >> n;
    tmp = n;
    while(tmp > 0){
        num += tmp%10;
        tmp /= 10;
    }
    if(n%num==0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

int main(){
  int *A,n,temp,i,j,flag,cnt=0;
    scanf("%d",&n);
   
 
  A =(int *)malloc(n * sizeof(int));
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
     
  }
  flag = 1;
  i = 0;
  while(flag){
    flag = 0;
    for(j=n-1;j>=i+1;j--){
      if(A[j]<A[j-1]) {
	temp = A[j-1];
	A[j-1] =A[j];
	A[j] = temp;
	flag = 1;
	cnt++;
      }
    }
    i++;
  

  }
  for(i=0;i<n;i++){
    if(i==n-1) printf("%d",A[i]);
    else if(A[i]>9) printf("%-3d",A[i]);
    else printf("%-2d",A[i]);
  
    
  }
  printf("\n");
  printf("%d\n",cnt);
  free(A);
    return 0;


}



Measured memory_bytes: 2108
w, h, n = map(int, input().split())
xya = [list(map(int, input().split())) for _ in range(n)]

width = [0, w]
height = [0, h]

for x, y, a in xya:
    if a == 1:
        width = [max(width[0], x), width[1]]
    elif a == 2:
        width = [width[0], min(width[1], x)]
    elif a == 3:
        height = [max(height[0], y), height[1]]
    elif a == 4:
        height = [height[0], min(height[1], y)]

ans = max(0, width[1] - width[0]) * max(0, height[1] - height[0])
print(ans)


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

int main() {
  int N,K;
  cin >> N >> K;
  
  vector<int> H(N);
  int64_t sum=0;
  
  for(int i=0; i<N; i++)
    cin >> H.at(i);
  
  sort(H.begin(), H.end());
  
  if(N<=K)
    cout << 0 << endl;
  
  else{
     for(int i=0; i<N-K; i++){
       sum+=H.at(i);
     }
    cout << sum << endl;
  }
}

Measured memory_bytes: 1024
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int64_t, int64_t>;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int64_t N, K;
  cin >> N >> K;
  // const int64_t L = static_cast<int64_t>(T.length());
  vector<int64_t> H(N);
  for (int64_t i = 0; i < N; ++i) {
    cin >> H[i];
  }
  vector<int64_t> costs(N, INT64_MAX);
  costs[0] = 0;
  for (int64_t i = 0; i < N; ++i) {
    for (int64_t j = 1; j <= K; ++j) {
      if (i + j < N) {
        costs[i + j] = min(costs[i + j], costs[i] + abs(H[i + j] - H[i]));
      }
    }
  }
  cout << costs[N - 1] << endl;
  return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const long double eps = 1E-14;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

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

template<typename T>
struct Segment_Tree {
	typedef function<T(T, T)> F;

	ll n;
	F f;//モノイドとしての演算(最小値、和　など)
	T unit;//単位元

	ll size;
	vector<T> seg;

	Segment_Tree(ll n0, F f0, T unit0) {
		n = n0;
		f = f0;
		unit = unit0;

		size = 1;
		while (size < n) {
			size *= 2;
		}
		seg.assign(2 * size, unit);
	}


	void update(ll k, T x) {//k番目の要素をxに更新
		k += size - 1;
		seg[k] = x;
		while (k > 1) {
			k /= 2;
			seg[k] = f(seg[2 * k], seg[2 * k + 1]);
		}
	}



	T query_prep(ll a, ll b, ll k, ll l, ll r) {//[a,b)とkに対応する区間[l,r)の共通部分でクエリ
		if (b <= l || a >= r) { return unit; }
		if (a <= l && r <= b) { return seg[k]; }

		T v1 = query_prep(a, b, 2 * k, l, (l + r) / 2);
		T v2 = query_prep(a, b, 2 * k + 1, (l + r) / 2, r);
		return f(v1, v2);

	}

	T query(ll a, ll b) {
		return query_prep(a, b, 1, 1, size + 1);
	}

};




int main() {
	ll x[6];
	repn(i, 5) cin >> x[i];
	repn(i, 5) { if (x[i] == 0) { cout << i << endl; } }
}

Measured memory_bytes: 3644
N, M = map(int, input().split())

M_MAX = (N - 1) // 2

pos = 1
size = M_MAX
i = 0
while i < M and size > 0:
    print(pos, pos + size)
    pos += 1
    i += 1
    size -= 2

pos = 1 + M_MAX + 1
size = M_MAX - 1
while i < M and size > 0:
    print(pos, pos + size)
    pos += 1
    i += 1
    size -= 2

Measured memory_bytes: 9300
#include<stdio.h>
#include<stdlib.h>
void swap(int *,int,int);
int partition(int **,int,int);
void quicksort(int **,int,int);

int main(){
  int i,n,flag=0,**cord;
  scanf("%d",&n);
  cord = malloc(sizeof(int *)*3);
  for(i=0;i<3;i++)cord[i] = malloc(sizeof(int)*n);

  for(i=0;i<n;i++){
    getchar();
    cord[0][i] = getchar();
    getchar();
    scanf("%d",&cord[1][i]);
    cord[2][i]=i;
  }
  
  
  quicksort(cord,0,n-1);

  for(i=1;i<n;i++){
    if(cord[1][i-1]==cord[1][i]){
      if(cord[2][i-1] > cord[2][i])flag=1;
    }
  }
  if(flag == 1)printf("Not stable\n");
  else printf("Stable\n");
  for(i=0;i<n;i++){
    
    printf("%c %d\n",cord[0][i],cord[1][i]);
  }

  free(cord[0]);
  free(cord[1]);
  free(cord[2]);
  free(cord);
  return 0;
}

void  quicksort(int **cord,int p,int r){
  int q,i;
  if(p < r){
    q = partition( cord, p, r);
    quicksort( cord, p, q-1);
    quicksort( cord, q+1, r);
  }
}
int partition(int **cord,int p,int r){
  int i,j,X,tmp;

  X=cord[1][r];
  i=p-1;
  for(j=p;j<=r-1;j++){
    if(X >=cord[1][j]){
      i++;
      swap(cord[0],i,j);
      swap(cord[1],i,j);
      swap(cord[2],i,j);      
    }
  }
  swap(cord[0],i+1,r);
  swap(cord[1],i+1,r);
  swap(cord[2],i+1,r);    
  return i+1;
}

void swap(int *cord,int i,int j){
  int tmp;
  tmp = cord[i];
  cord[i] = cord[j];
  cord[j] = tmp;
}


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

int main() {
  char c;
  cin >> c;
  if ((c=='a')||(c=='i')||(c=='u')||(c=='e')||(c=='o')){
    cout << "vowel"<<endl;
  }
  else{
   cout << "consonant"<<endl;
  }
}

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

#define MAX 1000

void initialize();
int isEmpty();
int isFull();
void  push(int x);
int pop();

int top;
int S[100];

int main(){
  int x,n1,n2;
  char s[100];

  while( scanf("%s", s) != EOF ){

    if ( s[0] == '+' ){
      n1 = pop();
      n2 = pop();
      push(n1 + n2);
    } else if ( s[0] == '-' ){
      n1 = pop();
      n2 = pop();
      push(n2 - n1);
    } else if ( s[0] == '*' ){
      n1 = pop();
      n2 = pop();
      push(n1 * n2);
    } else {
      x = atoi(s);
      push(x);
    }
  }
  printf("%d\n",pop());
  return 0;
}

void initialize(){
  top = 0;
}

int isEmpty(){
  return top == 0;
}

int isFull(){
  return top >= MAX - 1;
}

void  push(int x){
  if (isFull()) fprintf(stderr,"overflow\n");
  top++;
  S[top] = x;
}

int pop(){
  if (isEmpty()) fprintf(stderr,"underflow\n");
  top--;
  return S[top+1];
}

Measured memory_bytes: 548
N, K = gets.chomp.split.map(&:to_i)
XYS = readlines.map { |l| l.chomp.split.map(&:to_i) }

sorted_x = XYS.sort_by { |xy| xy[0] }
sorted_y = XYS.sort_by { |xy| xy[1] }

ans = (sorted_x[-1][0] - sorted_x[0][0]) * (sorted_y[-1][1] - sorted_y[0][1])

N.times do |xi|
  (xi+1...N).each do |xj|
    N.times do |yi|
      (yi+1...N).each do |yj|
        num = 0

        lx = sorted_x[xi][0]
        rx = sorted_x[xj][0]

        by = sorted_y[yi][1]
        uy = sorted_y[yj][1]

        b = sorted_y[yi]
        u = sorted_y[yj]
        next if !(lx..rx).include?(b[0]) || !(lx..rx).include?(u[0])

        sorted_x[xi..xj].each do |x, y|
          num += 1 if by <= y && y <= uy
        end
        ans = [ans, (rx - lx) * (uy - by)].min if num >= K
      end
    end
  end
end

p ans

Measured memory_bytes: 1788
#include<iostream>
#include<queue>

using namespace std;

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

struct Edge{int to, dis, cost;};

int main() {
  while (true) {
    int n, m;
    cin >> n >> m;
    if (n == 0 && m == 0) break;
    vector<Edge> edge[n];
    rep (i, m) {
      int u, v, d, c;
      cin >> u >> v >> d >> c;
      --u, --v;
      edge[u].push_back((Edge){v, d, c});
      edge[v].push_back((Edge){u, d, c});
    }
    priority_queue<pair<int ,int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
    que.push(make_pair(0, 0));
    int dis[n];
    rep (i, n) dis[i] = 1e9;
    while (!que.empty()) {
      pair<int, int> now = que.top();
      que.pop();
      if (dis[now.second] < now.first) continue;
      dis[now.second] = now.first;
      rep (i, edge[now.second].size()) que.push(make_pair(now.first + edge[now.second][i].dis, edge[now.second][i].to));
    }
    int res = 0;
    rep (i, n) if (i > 0) {
      int r = 1e9;
      rep (j, edge[i].size()) if (dis[i] == dis[edge[i][j].to] + edge[i][j].dis) r = min(r, edge[i][j].cost);
      res += r;
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 2668
#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;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> oset;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using ll = long long;

void test_case(){
	int n; cin >> n;
	ll sum = 0;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= n ; j++){
			for (int k = 1 ; k <= n ; k++){
				sum+=__gcd(__gcd(i,j),k);
			}
		}
	}
	cout<<sum<<"\n";
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T=1;
	//~ cin >> T;
	while(T--){
		test_case();
	}
	return 0;
}


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

typedef long long ll;

ll N, K;
vector<vector<ll>> Count[2];
ll R;

ll norm(ll p) { return min(max(0ll, p), 2 * K); }
ll calc(ll x, ll y, ll c) {
  ll x2 = x + K, y2 = y + K;
  x = norm(x);
  y = norm(y);
  x2 = norm(x2);
  y2 = norm(y2);
  ll res =
      Count[c][x2][y2] - Count[c][x2][y] - Count[c][x][y2] + Count[c][x][y];
  assert(res >= 0);
  return res;
}
int main() {
  cin >> N >> K;
  for (ll c : {0, 1}) {
    Count[c].resize(2 * K + 1);
    for (auto &count : Count[c]) count.resize(2 * K + 1);
  }
  for (ll i = 0; i < N; ++i) {
    ll x, y;
    char c;
    cin >> x >> y >> c;
    ++Count[c == 'W'][x % (2 * K) + 1][y % (2 * K) + 1];
  }
  for (ll c : {0, 1}) {
    for (ll y = 1; y <= 2 * K; ++y)
      for (ll x = 1; x <= 2 * K; ++x)
        Count[c][x][y] +=
            Count[c][x - 1][y] + Count[c][x][y - 1] - Count[c][x - 1][y - 1];
  }
  for (ll x = 0; x < 2 * K; ++x)
    for (ll y = 0; y < 2 * K; ++y) {
      ll r = 0;
      for (ll i = -2; i <= 1; ++i)
        for (ll j = -2; j <= 1; ++j) {
          r += calc(x + i * K, y + j * K, (i + j + 4) % 2);
        }
      R = max(R, r);
    }
  cout << R << endl;
  return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> p(N);
  for (int i= 0; i<N; i++) {
    cin >> p.at(i);
  }
  sort(p.begin(), p.end());
  long long int c = 0; 
  for(int i = N - 1; i >= 2; i--) {
    for (int j = i - 1; j >= 1; j--) {
      int s = p.at(i) - p.at(j);
      s++;
      if (j == 2) {
        if (s <= p.at(0)) {
          c++;
        }
        if (s <= p.at(1)) {
          c++;
        }
      }
      else if (j == 1) {
        if (s <= p.at(0)) {
          c++;
        }
      }
      else {
        int l = 0;
        int r = j - 1;
        int m= (r + l) / 2;
        while (r - l > 1) {
          if (p.at(m) < s) {
            l = m;
          }
          else {
            r = m;
          }
          m = (r + l) / 2;
        }
        if (p.at(r) < s) {
          c += 0;
        }
        else if (p.at(l) >= s) {
          c += j - l;
        }
        else {
          c += j - r;
        }
      }
    }
  }
  printf("%lld\n", c);
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**3
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    while True:
        n = I()
        if n == 0:
            break
        a = sorted([I() for _ in range(n)])
        r = sum(a[1:-1]) // (n-2)
        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())




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

int main() {
  int N;
  cin >> N;
  vector<string> s(N);
  int64_t score = 0;
  for (int i = 0; i < N; i++){
    cin >> s[i];
    sort(s[i].begin(), s[i].end());
  }
  sort(s.begin(), s.end());
  string pro = "";
  int64_t set = 1;
  for (int i = 0; i < N; i++){
    if (pro == s[i]){
      set += 1;
      if (i == N - 1){
        score += set * (set - 1) / 2;
      }
    }
    else {
      pro = s[i];
      score += set * (set - 1) / 2;
      set = 1;
    }
  }
  cout << score << endl;
}


Measured memory_bytes: 7552
#include <stdio.h>
int main(void){
	int N;
	scanf("%d",&N);
	if(N<=90&&N>=65){
	printf("1\n");
	}
	else if(N<=122&&N>=97){
	printf("2\n");
	}
	else{
		printf("0\n");
	}
	return 0;
}


Measured memory_bytes: 2120
class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fac = [1 for i in range(self.n + 1)]
        self.finv = [1 for i in range(self.n + 1)]
        for i in range(2, self.n+1):
            self.fac[i] = (self.fac[i - 1] * i) % self.mod
            self.finv[i] = (self.finv[i - 1] * pow(i, -1, self.mod)) % self.mod

    def comb(self, n, m):
        return self.fac[n] * (self.finv[n - m] * self.finv[m] % self.mod) % self.mod
        
def iparse():
    return list(map(int, input().split()))

def RLE(s):
    res = []
    prev = ""
    cnt = 0
    for e in s:
        if prev == "":
            prev = e
            cnt += 1
        elif prev == e:
            cnt += 1
        else:
            res.append((cnt,prev))
            prev = e
            cnt = 1
    res.append((cnt,prev))
    return res


if __name__ == "__main__":
    s = input()
    rle = RLE(s)
    # print(rle)
    print(len(rle)-1)

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

int length(int n)
{
    int i = 1;
    while (n != 0)
    {
        n = n / 10;
        ++i;
    }
    return i;
}

int main()
{
    int n, m, i, j, k = 1;
    cin >> n >> m;
    vector<int> p(m), y(m), ans1(n, 1), ans2(m, 0);
    map<int, pair<int, int>> mp;
    for (i = 0; i < m; ++i)
    {
        cin >> p[i] >> y[i];
        mp[y[i]] = make_pair(p[i], i);
    }
    for (auto q : mp)
    {
        ans2[q.second.second] = ans1[q.second.first - 1];
        ++ans1[q.second.first - 1];
        ++i;
    }
    for (i = 0; i < m; ++i)
    {
        for (j = 0; j <= 6 - length(p[i]); ++j)
        {
            cout << 0;
        }
        cout << p[i];
        for (j = 0; j <= 6 - length(ans2[i]); ++j)
        {
            cout << 0;
        }
        cout << ans2[i];
        cout << "\n";
    }
    return 0;
}

Measured memory_bytes: 9344
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>

#define rep(i,n)  for(int i = 0; i < (int)(n);    i++)
#define sz(x)     ((int)(x).size())
#define all(x)    (x).begin(),(x).end()

using ll = long long;

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

int f (int v) {
  if ( v == 0 ) return 0;
  int p = std::bitset<32>(v).count();
  return f( v%p ) + 1;
}

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int n; std::cin >> n;
  std::string s; std::cin >> s;

  // count p
  int p = 0;
  rep(i,sz(s)) if ( s[i] == '1' ) p++;

  // p+1
  int a = 0;
  if ( p != n ) {
    int x = 1;
    for(int i=sz(s)-1; i>=0; i--) {
      if ( s[i] == '1' ) a = (a + x)%(p+1);
      x = (x*2)%(p+1);
    }
  }

  // p-1
  int b = 0;
  if ( p >= 2 ) {
    int y = 1;
    for(int i=sz(s)-1; i>=0; i--) {
      if ( s[i] == '1' ) b = (b + y)%(p-1);
      y = (y*2)%(p-1);
    }
  }
  //std::cout << "\%p+1 : " << a << std::endl;
  //std::cout << "\%p-1 : " << b << std::endl;

  // p+1 : a, p-1 : b
  std::vector<int> ans(n);
  int t1 = 1, t2 = 1;
  for(int i=sz(s)-1; i>=0; i--) {
    if ( s[i] == '1' ) {
      if ( p == 1 ) ans[i] = 0;
      else {
        int next = (b-t1+(p-1))%(p-1);
        //std::cout << i << " : " << next << std::endl;
        ans[i] = f(next)+1;
      }
    }
    else {
      int next = (a+t2)%(p+1);
      //std::cout << i << " : " << next << std::endl;
      ans[i] = f(next)+1;
    }
    if ( p >= 2 ) t1 = (t1*2)%(p-1);
    t2 = (t2*2)%(p+1);
  }
  
  for(auto&& m : ans) std::cout << m << std::endl;

  return 0;
}




Measured memory_bytes: 4396
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
using P = pair<ll,ll>;

bool pairCompare(const P& firstElof, const P& secondElof)
{
    return firstElof.second > secondElof.second;
}
int main() {
    ll N,H;
    cin >> N >> H;
    vector<P> pairs(N);
    ll mab=0;
    ll maa=0;
    for(int i=0;i<N;i++){
        ll a,b;
        cin >> a >> b;
        mab+=b;
        maa = max(a,maa);
        pairs[i] = make_pair(a,b);
    }
    ll ct = 0;
    sort(pairs.begin(),pairs.end(),pairCompare);
    while(maa<=pairs[ct].second && ct<N && H>0){
        H-=pairs[ct].second;
        ct++;
    }
    if(H<=0) cout << ct << endl;
    else cout << ((H%maa==0) ? ct+H/maa : ct+H/maa + 1) << endl;
}

Measured memory_bytes: 1792
// ~/BAU/ACM-ICPC/Teams/Rampage/Abukhadijah
// ~/Remember,remember the 6th of March
#include <functional>
#include <iomanip>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include<complex>
#include <unordered_map>
#include<unordered_set>
#include <numeric>
#include <string>
#include<iostream>
#include <fstream>
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include<cmath>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n';
const double PI = acos(-1.0);
const double  EPS = 1e-11;
const ll MOD = 1000000007;
const int N = 109;
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
void fast()
{
	std::ios_base::sync_with_stdio(0);
}
int main()
{
	string s;
	cin >> s;
	int cnt = 0;
	if (s[0] != 'A')
	{
		puts("WA");
		return 0;
	}
	for (int i = 2; i < s.length() - 1; i++)
	{
		if (s[i] == 'C')
			cnt++;
	}
	if(cnt!=1)
	{
		puts("WA");
		return 0;
	}
	for (int i = 1; i < s.length()-1 ; i++)
	{
		if (s[i] == 'C')continue;
		if (isupper(s[i]))
		{
			puts("WA");
			return 0;
		}
	}
	if(isupper(s[s.length()-1]))
	{
		puts("WA");
		return 0;
	}
	puts("AC");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define P pair<ll, ll>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

void print(Vl vec){
    rep(i, 0, sz(vec)){
        if(i) cout << " ";
        cout << vec[i];
    }
    coel;
}

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


int main() {
    ll n, k; cin >> n >> k;
    vector<char> d(k);
    rep(i, 0, k) cin >> d[i];
    rep(i, n, 100005){
        string s = to_string(i);
        bool f = false;
        rep(j, 0, sz(s)){
            rep(l, 0, sz(d)){
                if(s[j]==d[l]) f = true;
            }
        }
        if(f) continue;
        co(i);
        return 0;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll INF = 1LL << 62;
const int inf = 1 << 30;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int X; cin >> X;
    ll sum = 0;
    rep(i, 1, X+1){
        sum += i;
        if(sum >= X){
            cout << i << endl;
            break;
        }
    }

    return 0;
}


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

int memo[31];

int culc_cmb( int n ){
    if( memo[n] ){
        return memo[n];
    }else{
        /*if( n == 3 ) return 4;
        else if( n == 2 ) return 2;
        else if( n == 1 ) return 1;*/
        return memo[n] = culc_cmb(n-3)+culc_cmb(n-2)+culc_cmb(n-1);
    }
}

int main(){
    memo[3] = 4;
    memo[2] = 2;
    memo[1] = 1;
    int n;
    while( cin >> n, n ){
        int ans;
        if( culc_cmb(n) % (365 * 10) ) ans =  culc_cmb(n) / (365 * 10) + 1;
        else ans =  culc_cmb(n) / (365 * 10);
        cout << ans << endl;
    }
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};
const int N=2e5+5,A=26;
int dp[N][A];
int32_t main(){
    string s;
    cin>>s;
    int n=sz(s);
    forn(j,A)dp[n][j]=1;
    for(int i=n-1;i>=0;--i){
        forn(j,A)dp[i][j]=dp[i+1][j];
        int c=s[i]-'a';
        int w=0;
        forn(j,A)if(dp[i][j]<dp[i][w])w=j;
        dp[i][c]=dp[i][w]+1;
    }
    int x=0;
    string ans;
    while(x<n){
        int w=0;
        forn(j,A)if(dp[x][j]<dp[x][w])w=j;
        char c=w+'a';
        ans+=c;
        while(x<n&&s[x]!=c)x++;
        x++;
    }
    cout<<ans<<'\n';
    return 0;
}

Measured memory_bytes: 44372
#include <stdio.h>

int main(void)
{
    int i, n, m, c;
    scanf("%d%d%d", &n, &m, &c);
    int a[n][m], b[m];

    for ( i = 0; i < m; i++)
        scanf("%d", &b[i]);
    
    for ( i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }

    int cnt = 0;
    for ( i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = 0; j < m; j++)
        {
            sum += a[i][j] * b[j];
        }
        if(sum + c > 0)
            cnt++;
    }

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

Measured memory_bytes: 128
N, M = map(int, input().split())

submit = [input().split() for i in range(M)]
ans = [[0, 0] for i in range(N)]

for i in range(M):
    tmp = int(submit[i][0]) - 1
    if submit[i][1] == 'AC' and ans[tmp][0] == 0:
        ans[tmp][0] += 1
    elif submit[i][1] == 'WA' and ans[tmp][0] == 0:
        ans[tmp][1] += 1

print(sum(ans[i][0] for i in range(N)), sum(ans[i][1] for i in range(N) if ans[i][0] == 1))

Measured memory_bytes: 42380
#!/usr/bin/ruby
Z=10**9+7
def d(x,y) x.zip(y).reduce(0){|s,(a,b)|s+a*b} end
def mul(x,y)
	y=y.transpose
	[[d(x[0],y[0])%Z,d(x[0],y[1])%Z],[d(x[1],y[0])%Z,d(x[1],y[1])%Z]]
end
def pow(x,y)
	z=1
	while y>0
		z=z*x%Z if y%2>0
		x=x*x%Z
		y/=2
	end
	z
end
H,W,K=gets.split.map(&:to_i)
if K==0
	p 1
	exit
end
K-=1
M=$<.map{|e|e.chomp.chars}
c=M.count{|s|s[0]=='#'&&s[-1]=='#'}
d=M.transpose.count{|s|s[0]=='#'&&s[-1]=='#'}
if c>0&&d>0
	p 1
	exit
end
if d>0
	c,d=d,c
	M=M.transpose
H,W=W,H
end
a=b=0
M.each{|s|W.times{|i|
	a+=1 if s[i]=='#'
	b+=1 if i<W-1&&s[i]=='#'&&s[i+1]=='#'
}}
if c==0&&d==0
	p pow(a,K)
	exit
end
 
e=[[1,0],[0,1]]
m=[[a,-b],[0,c]]
k=K
while k>0
	e=mul(e,m) if k%2>0
	m=mul(m,m)
	k/=2
end
p mul(e,[[1,0],[1,0]])[0][0]%Z
#p (e[0][0]+e[0][1])%Z

Measured memory_bytes: 97148