ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1193. Очередь на зачёт

WA #5
Послано Astekinane 23 сен 2011 01:06
Test my code, please.


#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int N;

bool proverka(vector <int> &used, queue <int> &Q){
    if (!Q.empty()) return true;
    for (int i=0;i<N;i++)
        if (!used[i]) return true;
    return false;
}

int main(){
    cin>>N;
    vector <int> T1(N);
    vector <int> T2(N);
    vector <int> T3(N);
    for (int i=0;i<N;i++)
        cin>>T1[i]>>T2[i]>>T3[i];
    vector <int> used(N,0);
    queue <int> Q;
    int res=0;
    int tres=0;
    for (int m=0;m<4*N;m++){
        int t=-1;
        for (int i=0;i<N;i++)
            if (!used[i] && (t==-1 || T1[i]<T1[t]))
                t=i;

        //cout<<t+1<<": "<<T1[t]<<" "<<T2[t]<<" "<<T3[t]<<" "<<Q.front()<<endl;
        if (Q.empty() && t==-1)
            continue;

        if (Q.empty()){
            res+=T1[t];
            used[t]=1;
            Q.push(t);
            for (int i=0;i<N;i++)
                if(!used[i]){
                    T1[i]-=T1[t];
                    if (T1[i]<=0){
                        Q.push(i);
                        used[i]=1;
                    }
                }
            continue;
        }

        if (t==-1){
            res+=T2[Q.front()];
            tres=max(tres,(res-T3[Q.front()]<0 ? 0 : res-T3[Q.front()]));
            Q.pop();
            continue;
        }

        if (T1[t]<T2[Q.front()]){
            res+=T1[t];
            used[t]=1;
            Q.push(t);
            for (int i=0;i<N;i++)
                if(!used[i]){
                    T1[i]-=T1[t];
                    if (T1[i]<=0){
                        Q.push(i);
                        used[1]=1;
                    }
                }
            T2[Q.front()]-=T1[t];
            if (T2[Q.front()]<=0)
                Q.pop();
            continue;
        }

        if (T1[t]>T2[Q.front()]){
            res+=T2[Q.front()];
            tres=max(tres,(res-T3[Q.front()]<0 ? 0 : res-T3[Q.front()]));
            for (int i=0;i<N;i++)
                if (!used[i]){
                    T1[i]-=T2[Q.front()];
                    if (T1[i]<=0){
                        Q.push(i);
                        used[1]=1;
                    }
                }
            Q.pop();
            continue;
        }

    }

    cout<<tres<<endl;
    return 0;
}